首页 > 代码库 > 乘法逆元
乘法逆元
1256 乘法逆元
基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题
给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。
Input
输入2个数M, N中间用空格分隔（1 <= M < N <= 10^9)
Output
输出一个数K，满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。
Input示例
2 3
Output示例
2
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;long long min(long long a,long long b){ if(a>b)return b; else return a;}int main(){ long long n,m; cin>>m>>n; long long ans=1000000000; for(long long i=1;i<n;++i) { if(i*m%n==1)ans=min(ans,i); } cout<<ans; puts(""); return 0;}
注意longlong
//能AC但是会T
正解exgcd
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;long long x,y;void ex_gcd(int a,int b){ if(b==0) { x=1; y=0; return; } ex_gcd(b,a%b); int temp=x; x=y; y=temp-a/b*y;}int main(){ long long n,m; scanf("%lld%lld",&n,&m); ex_gcd(n,m); printf("%lld",(x%m+m)%m); puts(""); return 0;}
乘法逆元
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。