收藏 
关注 给出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
显然，需要满足方程A*xx+B*yy=1+N。我的思路是使用扩展欧几里德求出大于零的最小值xx之后，取其remain=N-(xx)*A，再用remain除以A、B的最小公倍数即可。
感觉51nod上的题目对于算法的优化要求很高，很多时候一个不小心出来的结果TLE比WA都多，所以很多地方都要注意算法的时间啊。
代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;long long N,A,B,result,d,z,xx,yy;void ex_gcd(long long a,long long b,long long &xx,long long &yy)
{if(b==0){xx=1;yy=0;d=a;}else{ex_gcd(b,a%b,xx,yy);long long t=xx;xx=yy;yy=t-(a/b)*yy;}
}long long cal2()
{ result=0;ex_gcd(A,B,xx,yy);z=A*B/d;if((1+N)%d)return 0;else{xx=xx*((1+N)/d);long long r=B/d;xx = (xx%r+r)%r;if(xx==0)xx+=r;long long remain=N-(xx)*A;if(remain<0)return 0;else{result++;result += remain/z;}}return result;
}
int main()
{int count;scanf("%d",&count);while(count--){scanf("%lld%lld%lld",&N,&A,&B);cout<<cal2()<<endl;}return 0;
}
