乘法逆元线推

在信息学奥赛中，有这样一个问题：给定正整数 n与 p，求 1∼n 中的所有数在模 p意义下的乘法逆元，其中p是质数。详细题目见：https://loj.ac/problem/110

• 求一个数的逆元有两种求法，通过扩展欧几里得或者欧拉定理来求，如不会可点击链接https://blog.csdn.net/xuechen_gemgirl/article/details/77929143 学习
• 此题中求的是1~n中所有数的逆元，那么逆元线推就很好的O(n)时间复杂度内解决

---

逆元线推公式

inv(a) = ( p - p / a) * inv( p % a ) % p; (其中inv(i)表示i 的逆元)

证明

设 x = p % a,y = p / a; （y就是p/a的商， x就是p/a后的余数）
于是： x + y * a = p;
等式两边同时对p取余: （x + y * a）% p = 0;
去括号并移项：x % p = - y * a % p;
将a移至左边: inv (a) * x % p = - y % p;
　　　　　 　inv(a) * x % p = (-y + p ) % p;
将x移至右边 inv(a) =( p - y ) * inv(x) % p;
将证明开始设的x,y值代入上面式子中,则有 inv(a) = ( p - p/a )*inv( p % a ) % p;

标程

#include using namespace std; long long inv[3000006]; int main(){ int n,p; cin >> n >> p; inv[1] = 1; for(int i = 2;i<= n;i++){ inv[i] = (p - p/i) * inv[p%i] % p; } for(int i = 1;i<= n;i++){ scanf("%lld ",inv[i]); } return 0; } 希望此文能对你有所帮助。