luogu-P10570 [JRKSJ R8] 网球

题目传送门：

[JRKSJ R8] 网球 - 洛谷https://www.luogu.com.cn/problem/P10570

解题思路

        数学问题，暴力这个范围会超时。

        首先，找出这两个数的最大公因数，将这两个数分别除以最大公因数，则这两个数互质，判断如果有一方<=c，求出他们翻倍的倍数（ceil(c*1.0/min(a,b))），那么将他们分别乘ceil(c*1.0/min(a,b))（这里如果用循环会超时），即可求出a+b最小值，这里主要考察两个数除最大公因数为互质，即结果会最小。

代码

#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b)
{return b?gcd(b,a%b):a;
}
int main()
{long long t,a,b,c,r,x,y;for(cin>>t; t; t--){scanf("%lld%lld%lld",&a,&b,&c);r=gcd(a,b); //求出最大公因数，使他们互质 a/=r;b/=r;x=a;y=b;if(x < c || y < c){long long d = ceil(c*1.0/min(a,b)); //求出翻倍的倍数 x = d*a;y = d*b;}cout<<x+y<<endl; //输出 }return 0;
}