拓展欧几里得求 ax + by = c的通解（a >=0, b >= 0）

  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 // 题目：给定三种物品的价格A,B,C和拥有的钱P(C / gcd(A, B, C) >= 200)
 11 // 求解 AX + BY + CZ = P的解个数(case = 100)
 12 // A, B, C, P ∈ [0, 100000000]
 13 
 14 // 解：
 15 // AX + BY = P - CZ (C >= 200 -> Z <= 1e8 / 200 = 5e5)
 16 // 复杂度O(case * 5e5 * log(1e8))
 17 
 18 const int INF = 1e9;
 19 const ll MOD = 19940417;
 20 ll a, b, c, p, x, y, gcd_ab;
 21 
 22 ll exgcd(ll a, ll b, ll &x, ll &y)
 23 {
 24 
 25     if(b == 0){//推理1，终止条件
 26         x = 1;
 27         y = 0;
 28         return a;
 29     }
 30     ll r = exgcd(b, a%b, x, y);
 31     //先得到更底层的x2,y2,再根据计算好的x2,y2计算x1，y1。
 32     //推理2，递推关系
 33     ll t = y;
 34     y = x - (a/b) * y;
 35     x = t;
 36     return r;
 37 }
 38 
 39 ll fun(ll n)
 40 {
 41     if(n % gcd_ab) return 0;
 42     ll tim = n / gcd_ab;
 43     ll xx, yy;
 44     // a * (tim * x) + b * (tim * y) = gcd(a, b) * tim = n;
 45     xx = x * tim;
 46     yy = y * tim;
 47     ll k, k1, k2;
 48     //a * (xx + F) + b * (yy + G) = n
 49     // Fa + Gb = 0
 50     // F = lcm(a, b) / a * t
 51     // G = lcm(a, b) / g * t
 52     k1 = b / gcd_ab;
 53     k2 = a / gcd_ab;
 54 
 55     if(xx < 0){
 56         k = -(xx / k1) + (xx % k1 != 0);
 57         xx += k * k1; yy -= k * k2;
 58     }
 59     if(yy < 0){
 60         k = -(yy / k2) + (yy % k2 != 0);
 61         xx -= k * k1; yy += k * k2;
 62     }
 63 
 64     //cout << "aa = " << aa << " bb = " << bb << endl;
 65     ll x1, x2, y1, y2;
 66     if(xx < 0 || yy < 0) return 0;
 67     k = xx / k1;
 68     xx -= k * k1;
 69     yy += k * k2;
 70     x1 = xx, y1 = yy;
 71     k = yy / k2;
 72     xx += k * k1;
 73     yy -= k * k2;
 74     x2 = xx, y2 = yy;
 75     y2 = y2 - k * k2;
 76     //x1 + (x2 - x1) / k1 = x2
 77     return (x2 - x1) / k1 + 1;
 78 }
 79 
 80 void solve()
 81 {
 82 
 83     int T, _case = 0;
 84     cin >> T;
 85     while(T--){
 86         
 87         cin >> a >> b >> c >> p;
 88         //ax + by = gcd(a, b)
 89         gcd_ab = exgcd(a, b, x, y);
 90         //cout << x << " " << y << endl;
 91         ll ways = 0;
 92         for(ll i = 0; p - c * i >= 0; ++i){
 93             ways += fun(p - c * i);
 94             //cout << "ways = " << ways << endl;
 95         }
 96 
 97         cout << "Case " << ++_case << ": " << ways << endl;
 98     }
 99 }
100 
101 int main()
102 {
103 
104     solve();
105 
106     //cout << "ok" << endl;
107 
108     return 0;
109 }