CF 1095C Powers Of Two（二进制拆分）

A positive integer xx is called a power of two if it can be represented as x=2y, where y is a non-negative integer. So, the powers of two are 1,2,4,8,16,…

You are given two positive integers nn and k. Your task is to represent nn as the sumof exactly k powers of two.

Input

The only line of the input contains two integers nn and k (1≤n≤109, 1≤k≤2?105).

Output

If it is impossible to represent nn as the sum of k powers of two, print NO.

Otherwise, print YES, and then print kk positive integers b1,b2,…,bk such that each of bibi is a power of two, and ∑i=1kbi=n. If there are multiple answers, you may print any of them.

Examples

Input

9 4

output

Copy

YES
1 2 2 4 

input

Copy

8 1

output

Copy

YES
8 

input

Copy

5 1

output

Copy

NO

input

Copy

3 7

output

Copy

NO

题意

• 判断一个数n是否可以由k个2的p次幂来组成，p为自然数，p任取。

• 第一大类情况，判断有没有组成可能

  • k过多，有些数会被轮空，极端情况下，n可以有n个2的0次幂来组成，而当k大于n时，会有多余的数。所以在这种情况也不可能组成。
  • k过少，n转换成二进制后中1的各数即这个数所需要1的个数的最少的个数，若k少于这个个数，那么不可能组成。

• 第二大类情况，如果有组成的可能

  • 刚刚好
  • 没刚刚好，在二进制中，高位的1可以由两个低一位的1来组成。注意这里要从最高位开始分解，若从中间开始分解，将达不到最大的k的范围（忽视了前面一的分解，将前面1给滞空了）

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
int main()
{
	int n,k;
	cin>>n>>k;
	
	int cnt2=0,p=0,a[1000];
	int copy=n;
	while(copy>0)
	{
		if(copy&1)
		   cnt2++;
		a[p++]=copy&1;
		copy=copy>>1;
	}
	
	if(k>n||cnt2>k)
	{
		cout<<"NO";
	}
	else
	{	
	    cout<<"YES"<<endl;
		if(cnt2==k)
		{
		}
		else
		{
			while(cnt2!=k)
			{
				for(int i=p-1;i>=1;i--)
				{
					if(a[i]>0)
					{
						a[i]-=1;
						a[i-1]=a[i-1]+2;
						cnt2++;
						if(cnt2==k)
						  break;
					}
				}
			}	
		}	
		
		for(int i=0;i<p;i++)
		{
			for(int j=0;j<a[i];j++)
			{
				cout<<int(pow(2,i))<<" ";
			}
		}
	}
	return 0;
}

注意：pow函数返回的是浮点数，超过一定位数后，会用科学计数法表示

CF 1095C Powers Of Two（二进制拆分）

原文：https://www.cnblogs.com/BeautifulWater/p/14882133.html