好的，我们先来看题：
同余方程
题目描述
求关于x的同余方程ax≡1(modb) 的最小正整数解。
输入输出格式
输入格式：一行，包含两个正整数 a,b，用一个空格隔开。
输出格式：一个正整数 x，即最小正整数解。输入数据保证一定有解。
输入输出样例
说明
【数据范围】
对于 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。
这道题如果像我刚刚说的暴力枚举，那么虽然时间复杂度只有O（n），但由于这道题出现了longlong范围的数据，暴力枚举一定会超时，那我们该怎么办呢？
很显然这道题的题意就是找到最小正整数x，使得ax%b=1，那么我们就可以得到这样一个式子：ax+by=1（这里的y是辅助答案，并且显然y只有是负整数时才能取到最小整数x）（PS：这里用加号是为了推导比较方便，同样可以用减号）
在这里我们用到了扩展gcd，来求出x和y值，针对这道题，我们需要详细推导一下过程：
由于ax+by=gcd(a,b)[x,y均为整数],那么gcd(a,b)=gcd(b,a%b)因此bx1+(a%b)y1=ax+by，由于a%b=a-(a/b)b,那么bx1+(a-a/b*b)y1=bx1+ay1-a/b*b*y1=ay1+b(x1-a/b*y1)=ax+by
所以x=y1 y=x1-a/b*y1
那么我们目标就转移到了求x1，y1上来，于是我们依次递归下去，直到我们可以找到一组确定的x1y1，那么这个x1y1是什么呢？
很显然：当我们不断递归下去下去，当b=0时就会停止递归（辗转相除法），那么此时的x1显然只能为1了，而y1显然可以取到任何数，但个人建议取到0，以免防止越界，因此我们再递归回来并用上刚刚推导得到的结论，就可以求出一组必然的解了。
请先不要兴奋。。。
后话，如果只想到这里，那么真的还不如枚举，因为一分也得不到！
这是为什么呢？
仔细读题，我们发现题中要求的并不是一组解，而是x的最小整数解，而由于我们求的x无法判断大小，可能为正或可能为负，那么我们只要不断加上b，或减b即可。
ax+by=1
ax + by + k*ba - k*ba = 1
a(x+kb) + (y-ka)b = 1
显然这样等式一定成立并且不会错过任何x值。
最后附上代码
1 #include<cstdio> 2 using namespace std; 3 long long x,y; 4 void exgcd(long long a,long long b) 5 { 6 if(b==0) 7 { 8 x=1; 9 y=0; 10 return; 11 } 12 exgcd(b,a%b); 13 long long x1=x,y1=y; 14 x=y1; 15 y=x1-y1*(a/b); 16 } 17 int main() 18 { 19 long long a,b; 20 scanf("%lld%lld",&a,&b); 21 exgcd(a,b); 22 if(x<0) 23 { 24 while(x<0) 25 { 26 x+=b; 27 } 28 } 29 else 30 { 31 while(x>0) 32 { 33 x-=b; 34 } 35 x+=b; 36 } 37 printf("%lld",x); 38 return 0; 39 }