题目链接: 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()就好啦~
代码:
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 void exgcd(int a, int b, int& x, int&y){
5 if(!b){
6 y=0, x=1;
7 return;
8 }else{
9 exgcd(b, a%b, x, y);
10 int temp=x;
11 x=y;
12 y=temp-a/b*y;
13 }
14 }
15
16 int main(void){
17 int m, n, x, y;
18 scanf("%d%d", &m, &n);
19 exgcd(m, n, x, y);
20 printf("%d
", (x+n)%n); //注意可能算出x为负数
21 return 0;
22 }