给出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
参见挑战程序设计第115页:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll extgcd( ll a,ll b,ll &x,ll &y){
ll d=a;
if(b){
d=extgcd(b,a%b,y,x);
y-=(a/b)*x;
}
else {
x=1;y=0;
}
return d;
}
ll modinv(ll a,ll mod){
ll x,y;
extgcd(a,mod,x,y);
return (mod+x%mod)%mod;
}
int main(){
ll m,n;
cin>>m>>n;
cout<<modinv(m,n)<<endl;
return 0;
}