转载

欧拉计划： 451. 模逆元

题目

Problem 451: Modular inverses

Consider the number 15.

There are eight positive numbers less than 15 which are coprime to 15: 1, 2, 4, 7, 8, 11, 13, 14.

The modular inverses of these numbers modulo 15 are: 1, 8, 4, 13, 2, 11, 7, 14

because

1*1 mod 15=1

2*8=16 mod 15=1

4*4=16 mod 15=1

7*13=91 mod 15=1

11*11=121 mod 15=1

14*14=196 mod 15=1

Let I(n) be the largest positive number m smaller than n-1 such that the modular inverse of m modulo n equals m itself.

So I(15)=11.

Also I(100)=51 and I(7)=1.

Find ∑I(n) for 3≤n≤2·10 ⁷

分析

根据题目，我们需要求解以下方程：

欧拉计划： 451. 模逆元

也就是：

欧拉计划： 451. 模逆元

这个方程显然有根 ±1，也就是 1 和 n-1。容易证明，对于素数 n，这就是全部的根了。也就是说，对于奇素数 n，I(n) = 1。对于合数，这个方程还有其他根。我们来推导一下：

欧拉计划： 451. 模逆元

如果 p 和 q 分别是 x-1 和 x+1 的因数，则存在正整数 a 和 b 使得：

欧拉计划： 451. 模逆元

令 c = ab, n = pq，则：

欧拉计划： 451. 模逆元

也就是说，如果 x 是小于 n-1 的最大整数，则，I(n) = x。

解答

根据以上分析，我们有以下 C++ 程序：

#include <iostream> #include <numeric> #include <vector>  int main() {   const int m = 20'000'000;   static int I[m + 1];   static std::vector<int> divisors[m + 1];   for (int i = 2; i <= m; I[i++] = 1)     for (int j = i; j <= m; j += i)       divisors[j].push_back(i);   long n;   for (int x = 2; x < m; x++)     for (auto p : divisors[x - 1])       for (auto q : divisors[x + 1])         if ((n = (long)p * q) > m) break;         else if (x < n - 1) I[n] = x;   std::cout << std::accumulate(I+3,I+m+1,0L) << std::endl; }

其中 divisors[i] 的值是一个向量，包含 i 的除 1 以外的所有因数。

这个程序的运行时间是 52 秒。

正文到此结束