← 完整题目索引

PROJECT EULER · #0274

可整除乘数

Divisibility Multipliers

仅题目 · 已解决原题 ↗

对于与 10 互质的每个整数 p>1,都有一个正整除乘数 m<p,它可以为任何正整数 n 上的以下函数保留 p 的整除性:

f(n)=(all but the last digit of n)+(the last digit of n)⋅m。

也就是说,如果 m 是 p 的整除乘数,则当且仅当 n 能被 p 整除时,f(n) 才能被 p 整除。

(当n远大于p时,f(n)将小于n,并且重复应用f为p提供乘法整除测试。)

例如,113 的整除乘数为 34。

f(76275)=7627+5⋅34=7797:76275和7797都可以被113整除。
f(12345)=1234+5⋅34=1404:12345和1404都不能被113整除。

与 10 互质且小于 1000 的质数的整除乘数之和为 39517。与 10 互质且小于 107 的质数的整除乘数之和是多少?

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。