codevs.cn/problem/1200/ (题目链接)
题意
求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。
Solution
这道题其实就是求${a~mod~b}$的逆元${x}$。所谓逆元其实很简单，记${a}$的关于模${p}$的逆元为${a^{-1}}$,则${a^{-1}}$满足${a*a^{-1}≡1(mod~p)}$，用扩展欧几里德即可。
代码
// uoj147
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<queue>
#define MOD 1000000007
#define inf 2147483640
#define LL long long
#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
using namespace std; void exgcd(int a,int b,int &x,int &y) {
if (b==0) {x=1;y=0;return;}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
int main() {
int a,b;
scanf("%d%d",&a,&b);
int x,y;
exgcd(a,b,x,y);
printf("%d",(x%b+b)%b);
return 0;
}