51 Nod 1352 集合计数

大致题意：求ax+by=n+1的正数解的个数。

先看下面:

相信看过了通解的参数表示后已经知道怎么解了，贴代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
void exgcd(ll a, ll b,ll &d, ll &x, ll &y) {
    if(!b){
        d = a;
        x = 1; y = 0;
    }else{
        exgcd(b, a%b, d, y, x);
        y -= x*(a/b);
    }
}
int main() {
    //freopen("in.txt","r",stdin);
    int t;
    scanf("%d", &t);
    while(t--) {
        ll a, b, x, y, n, d;ll ans=0;
        scanf("%lld%lld%lld",&n,&a,&b);
        exgcd(a,b,d,x,y);
        n++;
        if(n%d) {
            printf("0
");
            continue;
        }
        x*=(n/d);y*=(n/d);
        if(-((y*d)/a)>=(x*d)/b)ans=0;
        else {
            int L=ceil(-((y*d)*1.0/a));int R=floor((x*d)*1.0/b);
            if((y*d)%a==0)L++;if((x*d)%b==0)R--;
            ans=R-L+1;
        }
        printf("%lld
",ans);
    }
    return 0;
}