51nod

思路：本题相当于求 n+1 = Ax + By。求（x, y）。（x>0, y>0)

用扩展GCD求出一组解之后，通过这组解找到x>0的最小的解和y>0的最小的解，就可以求出一共有多少组解了。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 ll ex_gcd(ll a, ll b, ll &x, ll &y) {
 6     if(b == 0) {
 7         x = 1, y = 0;
 8         return a;
 9     }
10     ll r = ex_gcd(b, a%b, y, x);
11     y -= (a/b)*x;
12     return r;
13 }
14 int main() {
15     int T;
16     scanf("%d", &T);
17     while(T--) {
18         int n, a, b;
19         ll x=0, y=0;
20         scanf("%d%d%d", &n, &a, &b);
21         ll c = n + 1LL;
22         int t = __gcd(a, b);
23         if(c%t != 0) {
24             printf("0
"); continue;
25         }
26         c /= t, a /= t, b /= t;
27         ex_gcd(a, b, x, y);
28         x *= c, y *= c;
29         ll x1, x2, y1, y2;
30         if(x <= 0) {
31             ll o = (x+1)/b - 1, p = y/a;
32             x1 = x - o * b, y1 = y + o * a;
33             x2 = x + p * b, y2 = y - p * a;
34         } else {
35             ll o = x/b, p = (y+1)/a - 1;
36             x1 = x - o * b, y1 = y + o * a;
37             x2 = x + p * b, y2 = y - p * a;
38         }
39         ll ans = abs(x1-x2)/b + 1;
40         ans -= (x1<=0||y1<=0) + (x2<=0||y2<=0);
41         printf("%lld
", max(0LL, ans));
42     }
43     return 0;
44 }