乘法逆元讲解
目录
题目描述：
分析：
代码：
题目描述：
给定 n, p 求 1 ∼ n 中所有整数在模 p 意义下的乘法逆元。
这里 a 模 p 的乘法逆元定义为 ax ≡ 1 (mod p) 的解。
输入格式：
一行两个正整数 n, p。
输出格式：
输出 n 行，第 i 行表示 i 在模 p 下的乘法逆元。
分析：
令p = k * i + r (1 < r < i < p)，其中 k 是p / i的商, r 是余数
可得k * i + r ≡ 0 (mod p)
等式两边同时乘以i ^ {-1} * r ^ {-1}
可得k * r ^ {-1} + i ^ {-1} ≡ 0 (mod p)
即i ^ {-1} ≡ -k * r ^ {-1} ( mod p )
故：inv[i] = (p - p / i) * inv[p % i] % p
（其中， inv[i]表示 i 的逆元）
详情见代码。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 10;
//inv[i]表示i的逆元
int n, p;
long long inv[N];
int main() {
scanf("%d %d", &n, &p);
//1的逆元永远是本身
inv[1] = 1;
printf("1\n");
for(int i = 2; i <= n; ++i) {
//令p = k * i + r(1 < r < i < p)，其中k是p / i的商, r是余数
//可得k * i + r ≡ 0 (mod p)
//等式两边同时乘以i^{-1} * r^{-1}
//可得k * r^{-1} + i^{-1} ≡ 0(mod p)
//即i^{-1} ≡ -k * r^{-1}(mod p)
//故：inv[i] = (p - p / i) * inv[p % i] % p
inv[i] = (p - p / i) * inv[p % i] % p;
printf("%lld\n", inv[i]);
}
return 0;
}