题目链接: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1256
题意:中文题诶~
思路: M, N 互质, 求满足 K * M % N = 1 的最小k, 由这个式子我们可以得到y*N+1=k*M, 我们将这个式子变化一下, k*M+y'*N=1, 求最小的k, 就是求最小乘法逆元啦~
解这个式子我们直接用exgcd()就好啦~
代码:
#include <bits/stdc++.h>
using namespace std; void exgcd(int a, int b, int& x, int&y){
if(!b){
y=, x=;
return;
}else{
exgcd(b, a%b, x, y);
int temp=x;
x=y;
y=temp-a/b*y;
}
} int main(void){
int m, n, x, y;
scanf("%d%d", &m, &n);
exgcd(m, n, x, y);
printf("%d\n", (x+n)%n); //注意可能算出x为负数
return ;
}