拓展欧几里得

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <vector>
 5 
 6 using namespace std;
 7 
 8 #define ll long long
 9 
10 const int INF = 1e9;
11 
12 //裴蜀定理：若 ax + by = n 有解，则 gcd(a， b) | n
13 //拓展欧几里得：求 ax + by = gcd(a, b) 的解，通过辗转相除法得到一组特解：x0 y0
14 // 得到 ax + by = c 的特解：
15 // x = x0 * c / gcd(a, b)
16 // y = y0 * c / gcd(a, b)
17 // 通解:
18 // X = x + b / gcd(a, b) * t
19 // Y = y - a * gcd(a, b) * t   (t = 0, 1, 2, 3 ...) 
20 //最小非零解： x = (x % b + b) % b
21 // ax + by = gcd(a, b)
22 // ax + by + k * ab - k * ak = gcd(a, b)
23 // a(x + kb) + b(y - bk) = gcd(a, b)  ---->  x = (x % b + b) % b
24 
25 ll exgcd(ll a, ll b, ll &x, ll &y)
26 {
27 
28     if(b == 0){//推理1，终止条件
29         x = 1;
30         y = 0;
31         return a;
32     }
33     ll r = exgcd(b, a%b, x, y);
34     //先得到更底层的x2,y2,再根据计算好的x2,y2计算x1，y1。
35     //推理2，递推关系
36     ll t = y;
37     y = x - (a/b) * y;
38     x = t;
39     return r;
40 }
41 
42 void solve()
43 {
44 
45     //ax同余1(mod prime)  求最小正整数解
46     // ax + by = n ---> ax' + by' = gcd(a, b)
47     // k = gcd(a, b)  k*(ax' + by') = n
48     //以下 a, b, x, y对应上面 a, b, x', y' 
49     ll a, b, x, y;
50     scanf("%lld%lld", &a, &b);
51     exgcd(a, b, x, y);
52     printf("%lld
", (x % b + b) % b);
53 }
54 
55 int main()
56 {
57 
58     solve();
59 
60     return 0;
61 }