传送门
题意： 就是求ax+by=n+1有多少组正整数解
思路： 先用扩展欧几里得求出一组特解，然后处理得到最小的正的x。然后此时对应的y是最大的，再此基础上加减的次数便是解的个数，然后ax和by整个东西加减的差值是LCM，所以（lef-1）除以他再加1便是次数了，
#include<cstring> #include<string> #include<cstdio> #include<cstdlib> #include<iostream> #include<cmath> #include<algorithm> #include<queue> #include<vector> #include<map> #include<stack> #include<climits> #include<cctype> #include<bitset> #include<set> using namespace std; #define mod 1000000007 #define PI acos(-1.0) #define INF 0x3f3f3f3f typedef long long LL; LL a,b,n; LL extendGcd(LL a,LL b,LL &x,LL &y){ LL ans,t; if(b==0){ x=1;y=0; return a; } ans=extendGcd(b,a%b,x,y); t=x;x=y;y=t-(a/b)*y; return ans; } LL res(){ LL ret=0; LL x,y; LL gcd=extendGcd(a,b,x,y); if((n+1)%gcd)return 0; else { x=x*((n+1)/gcd); LL r=b/gcd; x=(x%r+r)%r; if(x==0)x=r; LL lef=n+1-a*x; if(lef<=0)return 0; else { ret++; ret+=(lef-1)/(a*b/gcd); } } return ret; } int main() { int T; scanf("%d",&T); while(T--){ scanf("%lld%lld%lld",&n,&a,&b); printf("%lld\n",res()); } return 0; }