题解：P10570 [JRKSJ R8] 网球

Alystkia · 2024-06-12 20:48:00 · 题解

思路

• 当没有最小值 c 的限制时，我们只需要求出 a 和 b 的最简比。

• 当有了最小值 c 的限制时，我们只需要适当扩倍就可以了。

解法

首先找出 a 和 b 的最大公约数 k，然后，用 k 除以 a 和 b，求出两个齿轮齿的最简比，再用 c 除以这两个比中较小的比，向上取整，最后用得到这个结果乘上两个比值，再相加就完事了。

代码

不开 long long 见祖宗

#include <bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int a,int b)
{
    if(a%b!=0)
        return gcd(b,a%b);
    else
        return b;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        int k=gcd(x,y);
        int x1=x/k,y1=y/k;
        int h=min(x1,y1);
        int ans=0;
        if(z%h==0)
            ans=z/h;
        else
            ans=z/h+1;
        cout<<ans*x1+ans*y1<<endl;
    }

    return 0;
}