传送门给出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示例25 2 410 2 3Output示例12解题思路:从集合可以看出,第一个元素是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:#inclu
...
继续阅读
(30)