← 完整题目索引

PROJECT EULER · #0451

模逆元

Modular Inverses

仅题目 · 待解原题 ↗

考虑数字 15。
有八个小于 15 的正数与 15 互质:1,2,4,7,8,11,13,14。
这些数字以 15 为模的模逆为:1,8,4,13,2,11,7,14
因为
1⋅1mod15=1
2⋅8=16mod15=1
4⋅4=16mod15=1
7⋅13=91mod15=1
11⋅11=121mod15=1
14⋅14=196mod15=1

令 I(n) 为小于 n−1 的最大正数 m,使得 m 模 n 的模逆等于 m 本身。
所以I(15)=11。
还有 I(100)=51 和 I(7)=1。

求 ∑I(n) 等于 3≤n≤2×107。

题解待补充

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