这题是 132 的延伸题
题目：（难度 50%）
定义 R(k) = 111...111 共 k 个 1
例如 R(6) = 111111
考虑 R(10^n), 例如 R(10), R(100), R(1000) 都不能被 17 整除，但 R(10000) 可以
而 19 不能整除任何 R(10^n)
问在 100000 以下不能整除任何 R(10^n) 的质数的和
防雷
考虑 R(1), R(2), ..., R(p+1)
根据鸽笼原理，一定存在 R(x) % p = R(y) % p 且 x < y <= p + 1
所以我们有 R(y) - R(x) = R(y-x) * 10^{y-x} = 0 (mod p)
对大于 5 的质数 p 而言，就有 R(y-x) = 0 (mod p)
所以 R(1), R(2), ..., R(p) 里至少有一个人会被 p 整除
令 R(a) 是最小的那个，则对于所有会被 p 整除的 R(b)
都有 R(b-a) = R(b-2a) = ... = 0 (mod p)
所以如果 b 不会被 a 整除的话，R(b%a) 就会是更小的解，矛盾
所以 R(a), R(2a), R(3a), ... 就是所有会被 p 整除的人
问题变成是否存在 10^n 能被 a 整除
这等价于 a 的质因子是不是只有 2 和 5
假如 a = 2^r * 5^s, 则我们只须要测试任何 R(10^k) 且 k >= max(r, s) 即可
因为 a <= p, 所以 r <= log2(p) 且 s <= log5(p) < log2(p)
因此对于质数 p 我们只须测试 R(10^{log2(p)}) 即可
接着用昨天的方法，计算
R(10^{log2(p)}) = (10^{10^{log2(p)}} - 1) * 9^{-1} (mod p)
看是否等于 0
最后遍历 < 100000 的质数即可