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
    
     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<
     
      <<'\n'<<1<<' ';    for(int i = t; i >= 1; i--)        cout<
      
       <<' ';    return 0;}