求ax%b = 1，即ax - by = 1；
很明显这是一个exgcd的形式。
那么要做这道题，首先需要gcd和exgcd的算法作铺垫。
gcd（辗转相膜法）：
int gcd(int a,int b){
if(b == ){
return a;
}
return gcd(b,a%b);
}
exgcd就是在求出gcd的基础上，求出ax+by = gcd(a,b)的一组x，y的解：
int exgcd(int a,int &x,int b,int &y){
if(b == ){
x = ;
y = ;
return a;
}
int g = exgcd(b,x,a%b,y);
int tx = x;
x = y;
y = tx -a/b*y;
return g;
}
这个算法的原理如下：
- 当b=0时，gcd(a,b) = a，ax+by 即 a*1 + 0*0 = gcd(a,b)；（因为b = 0，y的值其实不重要，这里就写成0）
- 因为gcd(a,b) = ax+by，gcd(b,a%b) = ax'+ by'，
每次递归时，gcd(a,b) = gcd(b,a%b)，所以ax+by = ax'+ by'，
并且已知 a%b = a-(a/b)*b，那么可以得到
ax'+by'
= bx + (a%b)y
= bx + (a-a/b*b)y
= bx + ay - (a/b)*by
= ay + b(x-(a/b)*y)
x'=y; y'=(x-(a/b)*y）
有了这些铺垫，再来看这道题：
ax+by=1，即gcd(a,b) = 1，说明a,b一定是互质的，方程才能有解（虽然知道了这个也没什么用orz）。
现在已经求出了一组x，y的解，怎么保证x是最小正整数呢？
已知
ax+by
= ax + by + k*ab - k*ab
= a(x+kb) + (y-ka)b
也就是说，当x改变b的整数倍时，原式的值可以保持不变；
那么最小正整数即为x%b；
但是要考虑x为负数的情况，就要先将x加上b，直到x为正数，再取模，可以得到
x = (x%b+b)%b;
完整代码如下
#include<cstdio>
using namespace std;
int a,b,x,y;
void exgcd(int a,int &x,int b,int &y){
if(b == ){
x = ;
y = ;
return;
}
exgcd(b,x,a%b,y);
int k = x;
x = y;
y = k-a/b*y;
return;
}
int main(){
scanf("%d%d",&a,&b);
exgcd(a,x,b,y);
x = (x%b+b)%b;
printf("%d",x);
return ;
}