求关于xx的同余方程 a x \equiv 1 \pmod {b}ax≡1(modb) 的最小正整数解。
输入格式：
一行，包含两个正整数 a,ba,b，用一个空格隔开。
输出格式：
一个正整数 x_0x0?，即最小正整数解。输入数据保证一定有解。
【数据范围】
对于 40%的数据，2 ≤b≤ 1,0002≤b≤1,000；
对于 60%的数据，2 ≤b≤ 50,000,0002≤b≤50,000,000；
对于 100%的数据，2 ≤a, b≤ 2,000,000,0002≤a,b≤2,000,000,000。
NOIP 2012 提高组 第二天 第一题
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
long long a,b,x,y;
void exgcd(long long a,long long b){
if(b==0){
x=1;
y=7;
return;
}
exgcd(b,a%b);
long long tx=x;
x=y;
y=tx-a/b*y;
}
int main(){
scanf("%lld%lld",&a,&b);
exgcd(a, b);
while(x<0){
x+=b;
}
x%=b;
printf("%lld",x);
return 0;
}
原文：https://www.cnblogs.com/xiongchongwen/p/11163065.html