Description
Beny 想要用蛋糕填饱肚子. Beny 一共想吃体积为 c 的蛋糕, 他发现有两种蛋糕可以吃, 一种体积为 a, 一种体积为 b, 但两种蛋糕各有特色. Beny 想知道他一共有多少种不同吃法, 使得他恰好可以填饱肚子.
Input
第一行一个 t
接下来 t 行, 每行三个正整数 a,b,c
Output
对于每个 a,b,c, 输出一个整数表示有几种不同吃法
Sample Input
样例输入 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
- Sample Output
样例输出 1
13
0
样例输出 2
- 6
- 2
- 135
- 3
- Data Constraint
对于 30% 的数据 t<=10,a,b,c<=100
对于 60% 的数据 t<=100,a,b,c<=10^9
对于 100% 的数据 t<=10000,a,b,c<=10^14
题解
其实就是求 ax+by=c 的非负整数解
显然 exgcd
先判断其是否有解, 设 a'=a/d,b'=b/d,c'=c/d
之后模拟求出所有解个数, 即 x+=b,y-=a
所以答案为 y/a+1
代码
- #include <cstdio>
- #include <iostream>
- #include <algorithm>
- #include <cmath>
- #include <cstring>
- #include <queue>
- #include <vector>
- #include <string>
- #include <memory.h>
- using namespace std;
- long long a,b,c,ans;
- long long exgcd(long long a,long long b,long long &x,long long &y)
- {
- if (!b)
- {
- x=1,y=0;return a;
- }
- long long e=exgcd(b,a%b,x,y),k=x;
- x=y;y=k-a/b*y;
- return e;
- }
- void doit(long long a,long long b,long long c)
- {
- long long x=0,y=0,d=exgcd(a,b,x,y);
- if (c%d)
- {
- printf("0\n");
- return;
- }
- long long p=b/d;
- x=((c/d%p*x)%p+p)%p,y=(c-a*x)/b;
- ans=y>=0?y/(a/d)+1:0;
- printf("%lld\n",ans);
- return;
- }
- int main()
- {
- freopen("cake.in","r",stdin);
- freopen("cake.out","w",stdout);
- int t; cin>>t;
- while (t--)
- {
- scanf("%lld%lld%lld",&a,&b,&c);
- doit(a,b,c);
- }
- return 0;
- }
[exgcd] Jzoj P5855 吃蛋糕
来源: http://www.bubuko.com/infodetail-2768143.html