拓展欧几里得

佚名 4年前 (2020-06-12) 算法 698人围观抢沙发百度已收录

 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 // 通解：
15 //x = x0 + (b / gcd(a, b)) * t
16 //y = y0 + (a / gcd(a, b)) * t   t = (0, 1, 2 ...)
17 // 那么通解 x1 = x * (n / gcd(a, b))  y1 = y * (n / gcd(a, b))
18 //就是 ax + by = n的通解 (gcd(a, b) | n) 
19 //最小非零解： x = (x % b + b) % b
20 // ax + by = gcd(a, b)
21 // ax + by + k * ab - k * ak = gcd(a, b)
22 // a(x + kb) + b(y - bk) = gcd(a, b)  ---->  x = (x % b + b) % b
23 
24 ll exgcd(ll a, ll b, ll &x, ll &y){
25     
26     if(b == 0){//推理1，终止条件
27         x = 1;
28         y = 0;
29         return a;
30     }
31     ll r = exgcd(b, a%b, x, y);
32     //先得到更底层的x2,y2,再根据计算好的x2,y2计算x1，y1。
33     //推理2，递推关系
34     ll t = y;
35     y = x - (a/b) * y;
36     x = t;
37     return r;
38 }
39 
40 void solve(){
41     
42     //ax同余1(mod prime)  求最小正整数解
43     ll a, b, x, y;
44     scanf("%lld%lld", &a, &b);
45     exgcd(a, b, x, y);
46     printf("%lld\n", (x % b + b) % b);
47 }
48 
49 int main(){
50     
51     solve();
52     
53     return 0;
54 }