題意：

給出N個(gè)固定集合{1，N},{2,N-1},{3,N-2},...,{N-1,2},{N,1}.求出有多少個(gè)集合滿(mǎn)足：第一個(gè)元素是A的倍數(shù)且第二個(gè)元素是B的倍數(shù)。

提示：

對(duì)于第二組測(cè)試數(shù)據(jù)，集合分別是：{1,10},{2,9},{3,8},{4,7},{5,6},{6,5},{7,4},{8,3},{9,2},{10,1}.滿(mǎn)足條件的是第2個(gè)和第8個(gè)。

第1行：1個(gè)整數(shù)T（1<=T<=50000)，表示有多少組測(cè)試數(shù)據(jù)。第2 - T+1行：每行三個(gè)整數(shù)N，A,B（1<=N，A，B<=2147483647)Output
對(duì)于每組測(cè)試數(shù)據(jù)輸出一個(gè)數(shù)表示滿(mǎn)足條件的集合的數(shù)量，占一行。Input示例
25 2 410 2 3Output示例
12
思路：
根據(jù)題意可以列出一個(gè)不定方程a*x+b*y=n+1，利用拓展gcd求一組可行解。要求出大于0的最小x，直接用所求出的一組可行解(x%(b/g) + (b/g))%(b/g)即可(其中g(shù)是a和b的最大公約數(shù))。這樣就求得了最小的a*x，那么剩下的就是n-a*x個(gè)數(shù)，x的通解形式是x+k*(b/g)，那么a*x的通解就是a*x+k*(a*b/g)==a*x+k*lcm，所以直接拿n-a*x除以lcm(a,b)再算上一開(kāi)始的那個(gè)最小的a*x就是最終答案。
代碼：
#include <bits/stdc++.h>using namespace std;typedef long long ll;ll extgcd(ll a, ll b, ll &x, ll &y) {    ll d = a;    if (b != 0) {        d = extgcd(b, a % b, y, x);        y -= (a / b) * x;    }    else {        x = 1; y = 0;    }    return d;}int main() {    int T;    scanf("%d", &T);    while (T--) {        ll n, a, b, x, y;        scanf("%I64d%I64d%I64d", &n, &a, &b);        ++n;        ll g = extgcd(a, b, x, y);        if (n % g) {            puts("0");            continue;        }        x *= n / g;        ll bb = b / g;        x = (x % bb + bb) % bb;        if (x == 0) x += bb;        if (a * x >= n) {            puts("0");            continue;        }        else {            ll lcm = a / g * b;            PRintf("%I64d/n", (n - 1 - x * a) / lcm + 1);        }    }    return 0;}