[閒聊] Euler 132
感覺還是要把想法寫下來 不然以後連話都不會講了
網站其實規定不能發解法 所以我會防雷
題目： （難度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%
--
此文章疑似使用AI技術合成，請謹慎甄別
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.77.61.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1692562276.A.336.html
推
08/21 04:14,
2年前
, 1F
08/21 04:14, 1F