P1082 同余方程

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 long long x,y;//目前方程真正的解 
 5 
 6 void exgcd(long long a,long long b)
 7 {
 8     //当前目的：求解 ax + by = gcd(a,b) 这么一个方程
 9 
10     if(b == 0) //a,b不断改变的过程中，b最终必然会成为0
11     {
12         //在 b = 0 时等式还要成立？ 使 x = 1,y = 0 ，必然成立 
13         x = 1;
14         y = 7; //建议返回0。不过y = 7能AC，证明了最后一个等式不受最后一个y影响
15         return;
16     } 
17 
18     exgcd(b,a % b);//把下一层系数传进去（先求下一个方程的解 ）
19 
20     //现在我们已经拿到了下一个方程的解x,y
21     long long tx = x;//暂时存一下x，别丢了
22     x = y;
23     y = tx - a / b * y; 
24 }
25 
26 int main()
27 {
28     long long a,b;
29     cin >> a >> b;
30     exgcd(a,b);
31 
32     while(x < 0)//我们求出来的x必然满足方程，但是不一定是最小正整数解
33         x += b;
34     x %= b;
35     //上面三行是“答案处理”，这里用while只是帮助理解，建议写成 x = (x % b + b) % b;
36     printf("%lldn",x);
37     return 0;
38 }