题意:给你一个数
很明显,看到这么大的数据范围,也只有二分这种 O(logN) 的能够做到了。
我们从特殊到一般分析,先随便一个数假设
那么
同理,我们再针对
如此循环下去,那么最后拆成的数就为:
所以我们可以用这种二分的方法来处理
没想到居然是到省选题。。。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
long long m;
long long ans[5010101],cnt;
int main()
{
scanf("%lld",&m);
while(m)
{
ans[++cnt]=m-m/2;
m/=2;
}
printf("%lld\n",cnt);
for(int i=cnt;i>=1;i--)
printf("%lld ",ans[i]);
return 0;
}