1352 集合计数
- 1.0 秒
- 131,072.0 KB
- 20 分
- 3级题
给出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个。
收起
输入
第1行：1个整数T（1<=T<=50000)，表示有多少组测试数据。
第2 - T+1行：每行三个整数N，A,B（1<=N，A，B<=2147483647)输出
对于每组测试数据输出一个数表示满足条件的集合的数量，占一行。输入样例
2
5 2 4
10 2 3输出样例
1
2
分析：
问题可以变成：Ax+By=n+1，然后扩展欧几里德可以求出最小解x0，最大解y0
然后对于最大的数By0减少一个lcm(A,B)就会出现一个答案（因为既要顾及a，又要顾及b），所以By0/lcm（A，B）就为最后的答案。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;LL exgcd(LL a, LL b, LL &x0, LL &y0)
{if(!b){x0 = 1; y0 = 0;return a;}int ans=exgcd(b, a%b, x0, y0);int t = x0;x0 = y0;y0 = t-a/b*y0;return ans;
}int main()
{LL n,a,b;int T;cin>>T;while(T--){scanf("%lld%lld%lld",&n,&a,&b);LL x0,y0;LL c=n+1; //ax+by=c 的解LL gcd=exgcd(a,b,x0,y0);LL lcm=a/gcd*b;if(c%gcd) printf("0\n");else {LL t=b/gcd;x0*=c/gcd;x0=(x0%t+t)%t;//cout<<x0<<endl;while(x0<=0) x0+=t;//最小的正整数解x LL By=c-x0*a;//s为b*y if(By<=0)cout<<"0"<<endl;else{//cout<<(n-a*x0)/lcm+1<<endl;if(By%a)cout<<1+By/lcm<<endl;elsecout<<By/lcm<<endl; }}}return 0;
}