初始有一个数n每过一秒所有大于1的数x都会分裂成3部分:⌊x2⌋ x2 ⌊x2⌋ ← 这个符号指floor取整问经过足够长的时间后即所有的数都是0或1的时候0的个数是多少
假设初始时有n个数字,经过一秒后,每个数字都会分裂成3个数字。所以经过1秒后,总共会有3n个数字。
对于每个数字x,经过一秒后,它会分裂成⌊x/2⌋,x%2,⌊x/2⌋三个数字。其中⌊x/2⌋表示x除以2的整数部分,x%2表示x除以2的余数。
当x为偶数时,x%2=0,所以分裂后的三个数字分别为⌊x/2⌋,0,⌊x/2⌋,即每个偶数会分裂成两个相同的数字。
当x为奇数时,x%2=1,所以分裂后的三个数字分别为⌊x/2⌋,1,⌊x/2⌋,即每个奇数会分裂成两个相邻的整数。
假设初始时有a个偶数和b个奇数,那么经过一秒后,会有2a个偶数和2b个相邻的整数。
继续推理,经过第二秒后,偶数会变成偶数或者两个相邻的整数,奇数会变成两个相邻的整数。
经过第三秒后,偶数会变成偶数、两个相邻的整数或者三个相邻的整数,奇数会变成两个相邻的整数或者三个相邻的整数。
可以看出,经过每秒后,数字的个数会增加一倍或者增加一倍加一(偶数变成两个相邻的整数)。
所以经过足够长的时间后,最后剩下的数字只有0或1,而且0的个数一定是2的幂次方。
假设最后剩下的数字有m个,那么经过足够长的时间后,初始时有n个数字,总共经过了k秒。
根据上面的推理,可以得到以下等式:2^k = n + m
因为最后剩下的数字只有0或1,所以m的取值范围为0到n。
所以问题可以转化为求满足2^k = n + m的非负整数k的个数。
根据上述等式,可以得到m = 2^k - n。
当m为非负整数时,k = log2(n + m)。
所以问题可以进一步转化为求满足m为非负整数时的k的个数。
可以通过遍历m的取值范围(0到n),计算对应的k值,来求解问题
原文地址: https://www.cveoy.top/t/topic/hWWE 著作权归作者所有。请勿转载和采集!