吃蛋糕题解

吃蛋糕题解

科技前沿 • 2025-03-08 08:21 • 阅读 22

大家好，我是讯享网，很高兴认识大家。

题目

题目描述

Beny 想要用蛋糕填饱肚子。Beny 一共想吃体积为 c 的蛋糕，他发现有两种蛋糕可以吃，一种体积为 a，一种体积为 b，但两种蛋糕各有特色。Beny 想知道他一共有多少种不同吃法，使得他恰好可以填饱肚子。

输入

输出

对于每个 a,b,c，输出一个整数表示有几种不同吃法。

样例输入

样例输入 1

讯享网

讯享网3 2 3 4 3 4 24 3 7 11

样例输入 2

讯享网4 12 13 1003 56 44 792 4616 5364    136

样例输出

样例输出 1

讯享网1 3 0

样例输出2

6 2 135 3

思路

题目大意我就不讲了。

她只吃两种蛋糕，a,b，我们设x表示第一种蛋糕吃x个，第二种蛋糕吃y个，则

讯享网

ax+by=c

这不就是扩展欧几里得马！

但当我们兴高采烈地区写代码时，我们发现一件事情：她问的是x,y共有多少组解，而不是最小解。

根据欧几里得定理，推出公式：方案总数= $|\frac{y}{a}|+1$ 。防负数留作思考。

而如果c|d不成立或y<0，那么输出0。

代码

讯享网#include <cstdio> #define ll long long using namespace std; ll a,b,c,d,x,y; void exgcd(ll a,ll b) { if (b==0) d=a,x=1,y=0; else { exgcd(b,a%b); ll t=x; x=y; y=t-a/b*y; } } int main() { int T; scanf("%d",&T); while (T--) { scanf("%lld %lld %lld",&a,&b,&c); exgcd(a,b); if (c%d) { printf("0\n"); continue; } a/=d,b/=d,c/=d; x=(((x%b)*(c%b))%b+b)%b; y=(c-a*x)/b; if (y<0) printf("0\n"); else printf("%lld\n",y/a+1); } return 0; }

吃蛋糕 题解

题目

题目描述

输入

输出

样例输入

样例输出

思路

代码

相关推荐