回首望月一波之前(logN)求逆元的扩展欧几里得算法
（求解(a * x equiv 1(Mod p)) (Leftrightarrow) 求解 (a * x + p * y = 1)）
LL exgcd(LL a,LL b,LL &x,LL &y){//注意引用
if(!b){x = 1,y = 0;return a;}
int d = exgcd(b,a % b,x,y);
LL temp = x;x = y;y = temp - y * (a / b);
return d;
}
int main(){
a = RD();p = RD();
LL d = exgcd(a,p,x,y);
printf("%d
",x);
return 0;
}
P3811 【模板】乘法逆元
题目背景
这是一道模板题
题目描述
给定n,p求1~n中所有整数在模p意义下的乘法逆元。
输入输出格式
输入格式：
一行n,p
输出格式：
n行,第i行表示i在模p意义下的逆元。
这次要求求出一串数的逆元之前的算法是(nlogN)的复杂度
但很显然承受不了，引入(O(N))求一串逆元的方法（模数(P)为质数）
[inv[1] = 1
]
[inv[{i}] = ({P - P / i}) * inv[P; \%;i];\% P
]
Code
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
typedef long long LL;
using namespace std;
int RD(){
int out = 0,flag = 1;char c = getchar();
while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
return flag * out;
}
const int maxn = 10000019;
int a,p;
LL x,y;
LL exgcd(LL a,LL b,LL &x,LL &y){
if(!b){x = 1,y = 0;return a;}
int d = exgcd(b,a % b,x,y);
LL temp = x;x = y;y = temp - y * (a / b);
return d;
}//放个扩欧一起好了（才不是什么第一次扩欧TLE了呢）
int inv[maxn];
int main(){
a = RD();p = RD();
inv[1] = 1;printf("1
");
for(int i = 2;i <= a;i++){
inv[i] = (LL)(p - p / i) * inv[p % i] % p;
printf("%d
",inv[i]);
}
return 0;
}