本文主要是介绍扩展欧几里得算法：吃蛋糕，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接

题目描述

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 的所有自然数解的个数。

这题还是有坑的，我们要注意两点：

1. 因为精度的问题， 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 。

2. 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;
}

写文章不易，望大家给 JG_DF_ 点个赞！

这篇关于扩展欧几里得算法：吃蛋糕的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！