题解：P10570 [JRKSJ R8] 网球（未成功）

题目链接

博客食用更佳 : My blog。

这道题不是很难。 提交记录

分析：

\(A\) 每转 \(a\) 圈，\(B\) 就转 \(b\) 圈，不考虑 \(c\) 的前提下，可知每个齿轮转了 \([a,b]\) 个齿，\(A\) 有 \([a,b] \div a\) 个齿，\(B\) 有 \([a,b] \div b\) 个齿，接着扩倍扩到都大于 \(c\)。

拓展：

这里要用辗转相除法，不知道戳这。

code：

#include <bits/stdc++.h>
#define in(t) t = read()
#define out(t) write(t);
using namespace std;
long long gcd(long long x, long long y) //求最大公因数
{
	if(x % y == 0) return y;
	return gcd(y, x % y);
}
inline void write(long long x)//数据太大了，快读快写
{
    if(x < 0)
	{
    	putchar('-');
		x = -x;
	}
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
inline long long read()
{
    long long f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9')
	{
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar();
    return f * x;
}

int main()
{
	long long t;
	in(t);
	while(t--)
	{
		long long a, b, c, lcm, mina, minb, xa, xb;
		in(a); in(b); in(c);
		lcm = a * b / gcd(max(a, b), min(a, b));//最小公倍数
		mina = lcm / a, minb = lcm / b;//不考虑c，a和b的最小旋转圈数
		xa = c / mina, xb = c / minb;
		if(xa * mina < c) xa++;//注意齿轮不够时再转一圈
		if(xb * minb < c) xb++;
		out(max(xa, xb) * (mina + minb));//为了对应上要取A，B转的圈数的最大值
		puts("");
	} 
	return 0;
}

完结~撒花