题目链接
题目描述
Beny 想要用蛋糕填饱肚子。Beny 一共想吃体积为 c 的蛋糕，他发现有两种蛋糕可以吃，一种体积为 a，一种体积为 b，但两种蛋糕各有特色。Beny 想知道他一共有多少种不同吃法， 使得他恰好可以填饱肚子。
输入
t第一行一个 t接下来 t 行，每行三个正整数 a,b,c
输出
对于每个 a,b,c，输出一个整数表示有几种不同吃法
样例输入
样例输入 1
3
2 3 4
3 4 24
3 7 11
样例输入 2
4
12 13 1003
56 44 792
4616 5364 836482148
3836501 7035978 77151863500136
样例输出
样例输出 1
1
3
0
样例输出 2
6
2
135
3
数据范围限制
对于 30%的数据 t<=10,a,b,c<=100对于 60%的数据 t<=100,a,b,c<=10^9对于 100%的数据 t<=10000,a,b,c<=10^14
做法
题目大意：给你三个数 a , b , c a,b,c a,b,c ，要你求出 a x + b y = c ax+by=c ax+by=c 的所有自然数解的个数。
小插曲：
本人感慨：哟！这不 exgcd 吗？几天不见，这么拉了？！
exgcd：鬼！
然后 exgcd 把我推出了 AC 的位置。。。
咳咳，回归主题。
我们首先用 exgcd 求出特殊解，然后判断 c c c 是否是 g c d ( a , b ) gcd(a,b) gcd(a,b) 的倍数，不是就直接输出 0 ，否则继续后面的操作。
我们让 a , b , c a,b,c a,b,c 同时除以 g c d ( a , b ) gcd(a,b) gcd(a,b) ，用来缩小数据范围，防止数据过大而爆掉。
之后求出 x x x 的最小自然数解，即 x = ( x x=(x x=(x% b + b ) b+b) b+b)% b b b ，接着求 y y y 的范围： 0 0 0 ~ ( c − a ∗ x ) / b (c-a*x)/b (c−a∗x)/b 。
我们由 a x + b y = c ax+by=c ax+by=c 而得出 x + = b , y − = a x+=b,y-=a x+=b,y−=a ，同样满足该方程，则 y y y 的方案数为 ( c − a ∗ x ) / b / a + 1 (c-a*x)/b/a+1 (c−a∗x)/b/a+1 ，即我们要求的 a x + b y = c ax+by=c ax+by=c 的所有自然数解的个数。
这题还是有坑的，我们要注意两点：
-
因为精度的问题， x = ( x x=(x x=(x% b + b ) b+b) b+b)% b b b 须扩展为 x = ( ( ( x x=(((x%b)*(c x=(((x% b ) ) b)) b))% b + b ) b+b) b+b)% b b b 。
-
y y y 可能会小于 0 0 0 ，当 y y y 小于的时候，就输出 0 0 0 ，否则输出 y / a + 1 y/a+1 y/a+1 。
至此，这道题就被解决完了。
#include<cstdio>
#define ll long long
ll t,a,b,c,k,x,y,tt;
void exgcd(ll a,ll b)
{
if(!b)
{
tt=a;//tt=gcd(a,b)
x=1;
y=0;
}
else
{
exgcd(b,a%b);
k=x;
x=y;
y=k-a/b*y;
}
return;
}
int main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld%lld",&a,&b,&c);
exgcd(a,b);//求出特殊解
if(c%tt)//判断c是否是gcd(a,b)的倍数
{
printf("0\n");
continue;
}
//让a,b,c同时除以gcd(a,b)
a/=tt;
b/=tt;
c/=tt;
x=(((x%b)*(c%b))%b+b)%b;//求出x的最小自然数解
y=(c-a*x)/b;//求y的范围
printf("%lld\n",y<0?0:(y/a)+1);//当y小于的时候，就输出0，否则输出y/a+1
}
return 0;
}