题目背景
这是一道模板题
题目描述
给定n,p求1~n中所有整数在模p意义下的乘法逆元。
输入输出格式
输入格式：
一行n,p
输出格式：
n行,第i行表示i在模p意义下的逆元。
输入输出样例
输入样例#1：
10 13
输出样例#1：
1
7
9
10
8
11
2
5
3
4
说明
1 \leq n \leq 3 \times 10 ^ 6, n < p < 200005281≤n≤3×106,n<p<20000528
输入保证 pp 为质数。
思路：求逆元，用inv(a)表示一个数的逆元。
特别注意：本题卡输出cout
方法一：费马小定理。
我们已知费马小定理为：a^≡1(mod p)
两边同时除以a得到 ：a^≡1/a(mod p)也就是a^≡inv(a) (mod p)
所以：inv(a)≡a^ (mod p)
然后就可以用快速幂求解。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,p;
long long pow(long long a,long long x,long long p){
long long s=%p;
for(;x;x>>=){
if(x&) s=s*a%p;
a=a*a%p;
}
return s;
}
int main(){
scanf("%d%d",&n,&p);
for(int i=;i<=n;i++)
cout<<pow(i,p-,p)<<endl;
}
费马小定理 时间复杂度n(log n) TLE
方法二：拓展欧几里得。
如果a*x+b*y=1在gcd(a,b)=1的情况下有解，那么这个解中的x就是a关于b的逆元，y就是b关于a的逆元。
证明：a*x%b+b%y%b=1%b;
a*x%b=1%b;
a*x≡1(mod b);
所以x是a关于b的逆元，同理，可证明y是b关于a的逆元。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,p;
void ex_gcd(long long a,long long b,long long &x,long long &y,long long &d){
if(!b){ x=;y=;d=a; }
else{
ex_gcd(b,a%b,y,x,d);
y-=x*(a/b);
}
}
int inv(long long t,long long p){
long long d,x,y;
ex_gcd(t,p,x,y,d);
return d==?(x%p+p)%p:-;
}
int main(){
scanf("%d%d",&n,&p);
for(int i=;i<=n;i++)
printf("%d\n",inv(i,p));
}
拓展欧几里得 83
方法三：因为p是一个质数，所以一定有inv(a)=(p-p/a)*inv(p%a)%p;
证明：设x=p%a,y=p/a;
于是有：(x+y*a)%p=0;
移项得：x%p=(-y)*a%p;
x*inv(a)%p=(-y)%p;
inv(a)=(p-y)*inv(x)%p;
所以：inv(a)=(p-p/a)*inv(p%a)%p;
然后一直递归到1为止。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 3000010
using namespace std;
int n,p;
int inv[MAXN];
int main(){
scanf("%d%d",&n,&p);
inv[]=;
printf("1\n");
for(int i=;i<=n;i++){
inv[i]=(p-p/i)*1ll*inv[p%i]%p;
printf("%d\n",inv[i]);
}
}
。。。