感覺還是要把想法寫下來 不然以後連話都不會講了
網站其實規定不能發解法 所以我會防雷
題目： （難度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%