在你面前撒个娇 哎呦喵喵喵喵喵
Description
我们一起学猫叫
一起喵喵喵喵喵
在你面前撒个娇
哎呦喵喵喵喵喵
我的心脏砰砰跳
迷恋上你的坏笑
你不说爱我我就喵喵喵
每当xjy和hqy一起唱起这首歌时，就会吸引好多猫群来听歌，这天他们又吸引来n群猫。
每个猫群里都分为雄猫和雌猫，第一个猫群里有1只雄猫和n只雌猫，第二个猫群里有2只雄猫和n-1只雌猫....第n个猫群里有n只雄猫和1只雌猫。
xjy和hqy都很喜欢猫，他们对猫分别有好感度a和b，当一个猫群的雄猫数是a的倍数时，这个猫群会对xjy产生好感，同样的，当一个猫群的雌猫数是b的倍数时，这个猫群会对hqy产生好感。
演唱结束后，他们想带一些猫群回他们自己的小窝，但是只有同时对xjy和hqy都产生好感的猫群才能被带走。
他们想知道能带走多少猫群，但xjy在hqy面前通常比较笨，所有只能求救于你了。
Input
第一行一个整数T,（1<=T<=50000），表示有T组测试样例。
之后T行，每行三个整数分别表示n，a，b（1<=n,a,b<=2147483647）
Output
共输出T行，每行对应一个测试数据，表示能带走的猫群数量。
Sample Input 1
2
5 2 4
10 2 3 Sample Output 1
1
2 Hint
对于第二个测试样例，可以带走的是2只雄猫9只雌猫的猫群和8只雄猫3只雌猫的猫群。
题意：表示选拔的时候死活一直错很迷，后来看了学长的代码，换了一种写法就对了，好迷呀，中文题，不解释啦~~
题解：这个题就是求方程 ax+by=n+1 的正整数解的个数，先跑一遍扩展欧几里得求方程 ax+by=gcd(a,b)的解，然后根据通解公式 x=x0*(n+1)/gcd+b*t/gcd ， y=y0*(n+1)/gcd-a*t/gcd(t 为整数) 可以计算出 x，y 的最小正整数解 x=(x0%(b/gcd)+(b/gcd) )%(b/gcd) ( x0 可能为负数,所以要加一个(b/gcd) ) y=(y0%(a/gcd)+(a/gcd) )%(a/gcd) ( y0 可能为负数,所以要加一个(a/gcd)) 不要问我为什么，记住就好了！然后就是，x的最小值对应y的最大值，根据 by=(n+1)-(a*x)求出y的最大值，然后根据通解公式可以知道y最大-y最小=y0*(n+1)/gcd-（y0*(n+1)/gcd-a*t最大/gcd=a*t最大/gcd 求出t最大，然后结果加一就好了。详细请看代码：
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
ll n,a,b,x,y;
ll ex_gcd(ll a, ll b, ll &x, ll &y){//扩展欧几里得模板
if(b==0){
x=1,y=0;
return a;
}
ll p=ex_gcd(b,a%b,y,x);
y-=a/b*x;
return p;
}
int main(){
int t;
cin >> t;
while(t--){
cin >> n >> a >> b;
ll gcd=ex_gcd(a,b,x,y);
ll ans=0;
if((n+1)%gcd==0){
ll k=(n+1)/gcd;
x*=k;//别忘记乘以(n+1)/gcd，因为所求x为ax+by=gcd(a,b)的解
y*=k;//别忘记乘以(n+1)/gcd，因为所求y为ax+by=gcd(a,b)的解
ll r1=b/gcd;
x=(x%r1+r1)%r1;
if(x==0) x=r1;//求出非0的x的最小解的
ll re=n+1-x*a;
if(re<=0) ans=0;
else{
ll yy=re/b;//y的最大解
ll r2=a/gcd;
y=(y%r2+r2)%r2;//求出非0的y的最小解
if(y==0) y=r2;
ans=(yy-y)/r2+1;//最大减最小除以a/gcd+1别忘记加一
}
}
cout << ans << endl;
}
return 0;
}
京公网安备 11010502036488号