对于a*x ≡ 1 (mod p) ，则称x为a的逆元，也即a在mod p下的倒数
所以对于 (a/b) mod p，我们可以先求出b的逆元，再与a相乘，再mod p即可
逆元的求法有多种，但线性推是最快的//对于求乘法逆元的模板题是最快的，但具体求某一个值就不行了（11.7upd）
线性推递推式:inv[i]=p-p/i*inv[p mod i]%p;
证明:
已知要求一个数的逆元;i*x ≡ 1 (mod p)
p=⌊p/i⌋*i+r r为余数
设⌊p/i⌋为k
则 k*i + r ≡ 0 (mod p)
同乘 1/i 和 1/r
则 k/r + 1/i ≡ 0 (mod p)
则有 1/i ≡ -⌊p/i⌋/(p mod i) (mod p)
前面已经说过一个数的逆元等于这个数在mod p 意义下的倒数
所以
inv[i] = -(p/i) / (p mod i) (mod p) (c++中int 自动向下取整
但我们要保证inv[i]为正数
所以可以加上一个p
因为p (mod p)=0,对结果没有影响
综上得到递推式 inv[i]=p-p/i*inv[p mod i]%p;
inv[0]=0,inv[1]=1;
代码实现:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; inline int read(){ int x=0; bool f=1; char c=getchar(); while(!isdigit(c)){if(c=='-')f=0;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} if(!f)return 0-x; return x; } ll inv[3000005]; int main(){ int n,p; n=read(),p=read(); inv[1]=1; printf("1\n"); for(int i=2;i<=n;i++){ inv[i]=(ll)p-(p/i)*inv[p%i]%p; printf("%lld\n",inv[i]); } } 欧拉定理如果a,p互质，那么a^φ(p) ≡ 1 (mod p)
若p为质数则有φ(p)=p-1
又因为a*x ≡ 1(mod p)
所以x=a^(p-2) (mod p)
再用快速幂求解即可 PS:用费马小定理也可证明
代码实现:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; ll quickpow(ll a,ll b,ll p){ ll ret=1; a%=p; while(b){ if(b%2)ret=ret*a%p; a=a*a%p; b>>=1; } return ret%p; } int QAQ; int main(){ ll n,p; scanf("%lld%lld",&n,&p); for(ll i=1;i<=n;i++){ ll t=quickpow(i,p-2,p); printf("%lld\n",t); } return QAQ; } 解同余方程a*x ≡ 1(mod p)等价于 求a*x+p*y=gcd(a,p)=1
用exgcd求解即可
代码实现:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; inline int read(){ int x=0; bool f=1; char c=getchar(); while(!isdigit(c)){if(c=='-')f=0;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} if(!f)return 0-x; return x; } int n,p,QAQ; void exgcd(int a,int b,int &x,int &y){ if(!b){ x=1,y=0; return ; } exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; } int main(){ n=read(),p=read(); for(int i=1;i<=n;i++){ int x,y; exgcd(i,p,x,y); cout<<(x%p+p)%p<<endl; } return QAQ; }
转载于:https://www.cnblogs.com/djhsbdb/p/9866469.html
