luogu P3811 【模板】乘法逆元
题目背景
这是一道模板题
题目描述
给定n,p求1~n中所有整数在模p意义下的乘法逆元。
输入输出格式
输入格式:
一行n,p
输出格式:
n行,第i行表示i在模p意义下的逆元。
输入输出样例
说明
1 ≤ n ≤ 3*106, n < p < 20000528 1≤n≤3×106,n<p<20000528
输入保证 pp 为质数。
(1)快速幂+费马小定理(nlogp)[常数较大]
#include<cstdio>
#include<iostream>
#include<algorithm>
#define LL long long
#define FOR(i,s,t) for(register int i=s;i<=t;i++)
using namespace std;
int n,p;
inline LL Fast_Power(int a,int b){
if(b==0)
return 1;
if(b==1)
return a;
LL ans=Fast_Power(a,b>>1);
ans=(ans*ans)%p;
return b&1?(ans*a)%p:ans;
}
int main(){
scanf("%d%d",&n,&p);
FOR(i,1,n)
printf("%lld\n",Fast_Power(i,p-2));
return 0;
}
(2)exgcd求线性方程[常数较小]
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#define BIG 100011
#define ll long long
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
using namespace std;
ll ansx,ansy,n,p;
inline ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b)
return a,x=1,y=0;
ll s=exgcd(b,a%b,y,x);
y-=a/b*x;
return s;
}
int main(){
cin>>n>>p;
FOR(i,1,n){
exgcd(i,p,ansx,ansy);
printf("%lld\n",(ansx+p)%p);
}
return 0;
}
(3).线性算法O(n)
递推式 f[i]=p-p/i*f[p%i]%p.
证明:
pΞk*i+r(mod p)
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)
f[i]=p-p/i*f[p%i]%p.
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#define BIG 100011
#define ll long long
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
using namespace std;
ll n,p;
ll f[3000011];
int main(){
cin>>n>>p;
f[1]=1;
puts("1");
FOR(i,2,n){
f[i]=(p-p/i)*f[p%i]%p;
printf("%lld\n",f[i]);
}
return 0;
}