首页 > 代码库 > [51nod1256]乘法逆元
[51nod1256]乘法逆元
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1256
解题关键：设$m \in {N_ + }$，则$a$在模$m$的意义下存在唯一的逆元，若$(a,m) \ne 1$，则$a$没有模$m$的逆元；
法一：费马小定理求解${a^{\phi (p)}} = 1\bmod p$
1 #include<bits/stdc++.h> 2 #define PI acos(-1.0) 3 using namespace std; 4 typedef long long ll; 5 ll mod_pow(ll x,ll n,ll p){ 6 ll res=1; 7 while(n){ 8 if(n&1) res=res*x%p; 9 x=x*x%p;10 n>>=1;11 }12 return res;13 }14 ll euler_phi(int n){15 int res=n;16 for(int i=2;i*i<=n;i++){17 if(n%i==0){18 res=res/i*(i-1);19 while(n%i==0) n/=i;20 }21 }22 if(n!=1) res=res/n*(n-1);23 return res;24 }25 26 27 int main(){28 int a,b;29 cin>>a>>b;30 ll m=euler_phi(b)-1;31 ll ans=mod_pow(a,m,b);32 cout<<ans<<endl;33 return 0;34 }
法二：拓展欧几里得算法求解
注意x可能为负，但不会超过-b
1 #include<bits/stdc++.h> 2 #define PI acos(-1.0) 3 using namespace std; 4 typedef long long ll; 5 ll x,y; 6 ll extgcd(ll a,ll b,ll &x,ll &y){ 7 ll d=a; 8 if(b){ 9 d=extgcd(b,a%b,y,x);10 y-=a/b*x;11 }12 else{13 x=1,y=0;14 }15 return d;16 }17 int main(){18 int a,b;19 cin>>a>>b;20 extgcd(a,b,x,y);21 cout<<(x+b)%b<<endl;22 return 0;23 }
[51nod1256]乘法逆元
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。