[閒聊] Euler 133
這題是 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 的質數即可
--
此文章疑似使用AI技術合成，請謹慎甄別
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.77.61.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1692644417.A.033.html