【HNOI2006】【Luogu2320】鬼谷子的钱袋（进制，玄学）

problem

把一个数n进行拆分
拆分出来大于一的数两两不等，使得拆出来的数可以组成[1, n]间的所有数
求最少拆成多少个数及拆分方案。n <= 1000000000。

solution

记得之前bz上好像水过这题，看了题解，答案就是二进制的位数，，，当时觉得好有道理，，然后就交了，，也没看。。。不过好像，不会证明还是，，，，

然后这次，，我还是全网都没找到证明，，所以继续占坑待填。。。。
讲个找规律的例子，比较好理解。

举个例子：
我们可以假象一下 若m=12 则需要求得组合方案有（1 2 3 4 ……12）
我们可以把他们分成两份 （1 2 …… 6） （7 8 ……12）称左边的为L 右边的为R
很容易得知R中的每种方案都可以由（12/2）+左边的组合得出
再次分成两份（1 2 3）（4 5 6）
同理 当m为奇数时 显而易见地 只需把 (m/2)改为（m/2+1） 即可

所以结论是：
表示n以内的任何数字可以用1到n/2内的数字
那么表示n/2以内的任何数字可以用1到n/4以内的数字……
答案就是不断n/2的结果。。（数值上等于二进制位数）

codes

#include<iostream>
using namespace std;
int t, a[100005];
int main(){
    int m;  cin>>m;
    while(m/2 != 0){
        t++;
        if(m%2 == 0)a[t] = m/2;
        if(m%2 == 1)a[t] = m/2+1;
        m /= 2;
    }
    cout<<t+1<<'\n'<<1<<' ';
    for(int i = t; i >= 1; i--)
        cout<<a[i]<<' ';
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/81256989