UVA12775 Gift Dilemma（exgcd）

题目传送门

题意： 给定$T(T<=100)$组$A,B,C,P(A,B,C,P<=1e8)$，问你每组的数组中，有多少种方法使得$Ax+By+Cz=P$。保证$C/gcd(a,b,c)>=200$。

思路： 因为至少保证了$C/gcd(a,b,c)>=200$，我们可以枚举$z$，使得$Ax+By=P-Cz$。

1. $D=P-Cz$
2. $Ax+By=D$
3. 求出一组特解：$x,y$
4. 显然，$A(x-k\ast \frac{B}{gcd(A,B)})+B(y+k\ast \frac{A}{gcd(A,B)})=D$
5. $x-k\ast \frac{B}{gcd(A,B)}>=0,y+k\ast \frac{A}{gcd(A,B)}>=0$
6. $\lceil -y\ast \frac{gcd(A,B)}{A}\rceil <=k<=\lfloor x\ast \frac{gcd(A,B)}{B}\rfloor$

所以我们只需要提前算出$Ax+By=gcd(A,B)$的一组特解$x_0,y_0$，然后枚举$z$就行了。时间复杂度为$O(T\ast \frac{P}{C})$

代码：

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
char *fs,*ft,buf[1<<20];
#define gc() (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<20,stdin),fs==ft))?0:*fs++;
inline int read()
{
    int x=0,f=1;
    char ch=gc();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=gc();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=gc();
    }
    return x*f;
}
using namespace std;
// Author : ACfunhsl
// time : 2021/4/1 15:16:18
#define int long long
const int N=1e5+50;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;

int exgcd(int a,int b,int &x,int &y)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	int res = exgcd(b,a%b,x,y);
	int t = x;
	x = y;
	y = t - (a/b) * y;
	return res;
}
signed main()
{
	int t;
	cin>>t;
	int cas = 1;
	while(t--)
	{
		int a,b,c,p;
		cin>>a>>b>>c>>p;
		int d = __gcd(a,b);
		int res=0;
		int x0,y0;
		exgcd(a,b,x0,y0);
		for(int i=0;i*c<=p;i++)
		{
			int k = p-i*c;
			if(k%d) continue;
			int x =x0 * k/d;
			int y =y0 * k/d;
			res += (floor(1.0*x*d/b)-ceil(-1.0*y*d/a)+1);
		}
		cout<<"Case "<<cas++<<": "<<res<<endl;
	}



	return 0;
}