给出N个固定集合{1，N},{2,N-1},{3,N-2},…,{N-1,2},{N,1}.求出有多少个集合满足：第一个元素是A的倍数且第二个元素是B的倍数。
提示：
对于第二组测试数据，集合分别是：{1,10},{2,9},{3,8},{4,7},{5,6},{6,5},{7,4},{8,3},{9,2},{10,1}.满足条件的是第2个和第8个。
Input
第1行：1个整数T（1<=T<=50000)，表示有多少组测试数据。
第2 - T+1行：每行三个整数N，A,B（1<=N，A，B<=2147483647)
Output
对于每组测试数据输出一个数表示满足条件的集合的数量，占一行。
Input示例
2
5 2 4
10 2 3
Output示例
1
2
解题思路:
从集合可以看出，第一个元素是i(1<=i<=N),第二个元素是N-i+1.对于第i个集合,那么我们现在设两个数分别是A*x,和B*y,那么一定满足A*x=i && B*y=N-i+1 (x>0,y>0)的i，那么第i个集合就成立。两式合并得：A*x+B*y=N+1;这式子可以用扩展GCD求出gcd，x和y，然后我们求出大于0的最小x，A*x第一个满足条件的集合firstSet，剩下的N-firstSet个集合可以直接除LCM(A,B)统计出数量。
My Code:
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
void Ex_gcd(LL a, LL b, LL &x, LL &y)
{
if(b == 0)
{
x = 1;
y = 0;
return;
}
LL x1, y1;
Ex_gcd(b, a%b, x1, y1);
x = y1;
y = x1 - (a/b)*y1;
}
LL GCD(LL a, LL b)
{
if(b == 0)
return a;
return GCD(b, a%b);
}
int main()
{
int T;
LL n, a, b, x, y;
scanf("%d",&T);
while(T--)
{
scanf("%I64d%I64d%I64d",&n,&a,&b);
n++;
LL tmp = GCD(a, b);
LL LCM = a/tmp*b;
if(n%tmp)
{
puts("0");
continue;
}
LL aa = a/tmp;
LL bb = b/tmp;
LL nn = n/tmp;
Ex_gcd(aa, bb, x, y);
x *= nn;
x = (x%bb+bb)%bb;
LL remin = n-1-x*a;
if(remin < 0)
puts("0");
else
cout<<1+remin/LCM<<endl;
}
return 0;
}