吃蛋糕

题目描述

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

输入格式

第一行一个 t

接下来 t 行，每行三个正整数 a,b,c

输出格式

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

样例

输入数据 1

3
2 3 4
3 4 24
3 7 11

输出数据 1

1
3
0

输入数据 2

4
12 13 1003
56 44 792
4616 5364 836482148
3836501 7035978 77151863500136

输出数据 2

6
2
135
3

数据规模与约定

对于 30%的数据 t<=10,a,b,c<=100

对于 60%的数据 t<=100,a,b,c<=10⁹

对于 100%的数据 t<=10000,a,b,c<=10¹⁴

 一看就可以看出来两种的蛋糕和吃的体积正好能够组成一个线性方程

很容易就会想到扩欧真挺容易的，儿豁

所求的就是该方程解的个数

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll ans,n,c;
ll ksm(ll a,ll b,ll mod){
    ll ret = 0;
    for(;b;b>>=1,a+=a,a%=mod)
        if(b&1)
            ret+=a;
    return ret;
}
ll gcd(ll a,ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}
void exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x = 1;
        y = 0;
        return ;
    }
    exgcd(b,a%b,x,y);
    ll t = x;
    x = y;
    y = t-(a/b)*y;
    return ;
}
int main(){
    ll a,b,x,y,d;
    scanf("%lld",&n);
    for(int i = 1;i<=n;i++){
        scanf("%lld%lld%lld",&a,&b,&c);
        d = gcd(a,b);
        if(c%d){
            puts("0");
            continue;
        }else{
            a/=d;
            b/=d;
            c/=d;
            exgcd(a,b,x,y);
            x = ksm(x,c%b,b);
            x = (x%b+b)%b;
            y = (c-a*x)/b;
            if(y<0) puts("0");
            else printf("%lld\n",y/a+1);
        }
    }
    return 0;
}