https://www.luogu.org/problemnew/show/P1082
同余方程是一个数学方程式。该方程式的内容为：对于一组整数Z，Z里的每一个数都除以同一个数m，得到的余数可以为0，1，2，...m-1,共m种。我们就以余数的大小作为标准将Z分为m类。每一类都有相同的余数。
题目描述
求关于x xx的同余方程 ax≡1(mod b) a x equiv 1 pmod {b}ax≡1(modb) 的最小正整数解。
输入输出格式
输入格式：
一行，包含两个正整数 a,ba,ba,b，用一个空格隔开。
输出格式：
一个正整数 x0x_0x0，即最小正整数解。输入数据保证一定有解。
输入输出样例
说明
【数据范围】
对于 40%的数据，2≤b≤1,0002 ≤b≤ 1,0002≤b≤1,000；
对于 60%的数据，2≤b≤50,000,0002 ≤b≤ 50,000,0002≤b≤50,000,000；
对于 100%的数据，2≤a,b≤2,000,000,0002 ≤a, b≤ 2,000,000,0002≤a,b≤2,000,000,000。
思路：
ax≡1(mod b), ax%b==1%b,1%b==1,
即 ax%b==1，
ax-1=by 即求ax-by=1的最小整数解。
因为a和b互质，所以a和-b也互质，所以它们的最大公约数为1，
所以可以通过扩展欧几里得来求解【存在 x , y 使得 gcd(a,b)=ax+by】存在x,y,使得gcd(a,-b)=ax+(-b)y=1。
通过扩展欧几里得求得的解可能是正数也可能是负数，而题中要求求出最小的整数解，
所以对求出的x要加以判断，
当x<0要不断+b 使其大于0（小于0便不是正整数解），
当x>b要%b 使其小于b（大于b便不是最小的解）,
当x>0&&x<b即为所求出的结果。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int a,b,x,y,gcd; 4 int exgcd(int a,int b,int &x,int &y) 5 { 6 if(b==0) 7 { 8 x=1; 9 y=0; 10 return a; 11 } 12 int r=exgcd(b,a%b,x,y); 13 int t=x; 14 x=y; 15 y=t-a/b*y; 16 return r; 17 } 18 int main() 19 { 20 cin>>a>>b; 21 int x=0,y=0; 22 gcd=exgcd(a,b,x,y); 23 while(x<0)x+=b; 24 while(x>b)x%=b; 25 cout<<x<<endl; 26 return 0; 27 }