感觉还是要把想法写下来 不然以后连话都不会讲了
网站其实规定不能发解法 所以我会防雷
题目： （难度45%）
定义 R(k) = 1111....1111, 总共 k 个 1
例如 R(10) = 1111111111 = 11 * 41 * 271 * 9091
问 R(10^9) 前 40 个质因子的和
防雷
我的作法是遍历质数然后一个一个看是否整除 R(10^9)
显然 2, 3 都不符合，考虑 p > 3
我们有 R(10^9) * 9 + 1 = 10^{10^9}
在 mod p 下就有 R(10^9) = (10^{10^9} - 1) * 9^{-1} (mod p)
因为 p > 3 所以 9 一定有反元素
收集完前 40 个整除的即可
在我的电脑上大约五秒可以跑完
感觉难度没有到 45%