以最后一次才是SET做测试
10亿内的结果，0次到7次的数字的个数
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
char buf = "\0";
int b = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
int count = {0, 0, 0, 0, 0, 0, 0};
int check(mpz_t n)
{
int i, s = 0;
char * BF = buf;
mpz_get_str(BF, 10, n);
for (i = 0; BF != '\0'; i ++)
{
s |= b - '0'];
if (s == 1023)
return (1);
}
return (0);
}
void main(void)
{
unsigned long i, j, c, pow10 = 10;
mpz_t n;
mpz_init(n);
for (i = 2; i <= 1000000000; i ++)
{
if (i == pow10)
{
printf("%10d:", pow10);
for (j = 0; j <= 7; j ++)
printf("%10d ", count);
printf("\n");
pow10 *= 10;
}
if (i % 10 != 0)
{
c = 0;
mpz_set_ui(n, i);
while (check(n) == 0)
{
mpz_pow_ui(n, n, 2);
c++;
}
count ++;
}
}
mpz_clear(n);
}
稍微修改下就能测试，所有幂是SET 的情况
如果是全部幂
则10亿内测试结果是
只有2需要6次平方
还有个别数字需要5次（仅12个），绝大部分最多4次
2次的最多，其次1次的，其次3次，其次4次
估计5次那些都是10^n + 1, 10^n - 1的
f := NestWhile[# + 1 &, 2,
Union@IntegerDigits@Nest[#^2 &, n, #] != Range &]
Module[{k = 5, data, arr, min, max},
data = Complement, 10^Range];
arr = f /@ data;
{
{min, max} = {Min, Max},
{Count, Count},
Extract],
Extract],
Tally
} // Column
] // Timing
这个题目的确有些歧义，可以理解为某一个平方数出现所有0-9的数字，也可以理解为0-9中任意数字只要出现在某一个平方数中就可以。不过从链接中题目给出的例子来看，原题是采用第二种方案。
显然，从计算角度来看，前面一个更加难处理。我们可以只讨论第二种方案。
首先，末尾数为0的数字可以全部不讨论。末尾数为5的数字可以分开独立考虑。
从经验数据来看，对于所有的数字，应该6次足够了。但是证明应该很难，那我们是否可以适当降低难度，比如证明对于所有的数字，10次足够了，或者证明20次足够了？
比如我们为了证明20次以内可以对所有数据成立，
我们将所有数据可以分成3类:
i)5结尾的数
ii)末尾数非0的偶数
iii)末尾数非5的奇数。
现在以第3类为例子讨论，
如果我们能够证明对于某个h,($1<=h<20$),对于所有X,$X^{2^h}$到$ X^{2^20}$的最后k位可以覆盖0~9就可以了。
首先，我们知道对于第三类数,$X^{2^h}-=1(mod 2^{h+2})$,所以穷举这批数的最后k位，我们需要穷举
${10^k}/{2^{h+2}}$种不同的情况，我们希望这个数值不会太大。
其次，我们知道对于所有这些平方数，最末尾数总是1，所以实际贡献不同数字的有效位数只有$(21-h)*(k-1)$位，我们希望这个数字尽量大，那么最后余下的数字会更少）。
比如如果我们要求穷举空间不超过$10^10$个数据，那么可以选择k=13,h=8
也就是我们需要穷举所有类型iii)的整数的$2^8,2^9,...,2^19,2^20$次方的最后13位。
而我们知道这些数据的$2^8$的必然模$2^10$为1,同样它们模5为1，也就是模5120为1
所以我们可以选择穷举最后13为模5120为1的所有整数（把这个数看成一个数的$2^8$次方的最后13位）
然后再一次平方12次并只保留最后13位，得到所有13个数的末13位
然后我们查看这所有169位，如果覆盖0~9,那么我们证明了对于这种类型的数，最多平方到20次，必然完全覆盖0~9.而对于余下的数，我们还需要特殊处理。现在我们估计余下的数大概还有多少个:
由于我们知道这13个数最后一位必然是1，我们现在只考虑其余12*13=156位，它们不完全覆盖0~9的概率可以估算为$7*10^-7$,由于共穷举${10^13}/5120$个数，估计还留下1367总情况
接下去，我们需要再次分析这留下的一千多种情况：
这时，我们可以对着一千多种情况扩充位长，比如穷举这些情况的最末20位数的情况等等（也就是给定末13位，前面再任意添加7位数),然后再次得出新的7*13=91位，在利用它们进行淘汰；
如果还有数据剩余，可以继续这个过程。。。