给出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 using namespace std; //返回d=gcd(a,b);和对应于等式ax+by=d中的x,y long long extend_gcd(long long a,long long b,long long &x,long long &y) { if(a==0&&b==0) return -1;//无最大公约数 if(b==0){x=1;y=0;return a;} long long d=extend_gcd(b,a%b,y,x); y-=a/b*x; return d; } //*********求逆元素******************* //ax = 1(mod n) long long mod_reverse(long long a,long long n) { long long x,y; long long d=extend_gcd(a,n,x,y); if(d==1) return (x%n+n)%n; else return -1; } int main() { long long n,m; cin>>n>>m; cout<


q神的模板： #include #include #include #include #include #include using namespace std; int euler(int x) { int res=x; for(int i=2;i<=(int)sqrt(x);i++) { if(x%i==0) { res=res/i*(i-1); while(x%i==0)x/=i; } } if(x!=1) { res=res/x*(x-1); } return res; } int inv(int a,int p) { int res=1,t=euler(p)-1; while(t>0) { if(t&1)res=1LL*res*a%p; a=1LL*a*a%p; t>>=1; } return res; } int main() { int m,n; scanf("%d%d",&m,&n); printf("%d ",inv(m,n)); return 0; }