自动搬运

查看原文

来自洛谷，原作者为

	Alystkia 如果我再也见不到你，那么祝你早安，午安，晚安。

搬运于2025-08-24 22:59:16，当前版本为作者最后更新于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;
}