记录73
#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(){ int T; long long a,b,c,t; cin>>T; while(T--){ cin>>a>>b>>c; t=gcd(a,b); a/=t; b/=t; t=min(a,b); if(c%t==0) c/=t; else c=c/t+1; cout<<a*c+b*c<<endl; } return 0; }题目传送门https://www.luogu.com.cn/problem/P10570
突破口
你有两个啮合在一起的齿轮，你希望齿轮 A 每转 a 圈齿轮 B 都能转恰好 b 圈。
由于精细度要求，每个齿轮都必须有不少于c 个齿，求齿轮 A 和齿轮 B 的总齿数和的最小值。
思路
两个啮合齿轮：
- 齿轮 A 转
a圈 → 齿轮 B 转b圈 - 啮合齿轮的齿数与转速成反比：
A 的齿数：B 的齿数=b：a
B 的齿数：A 的齿数=a：b
即：
A_teeth:B_teeth=b:a
A_teeth:B_teeth=b:a
✅ 所以设：
- A 齿数 =
k * b- B 齿数 =
k * a
其中k是正整数（比例缩放因子）
约束：每个齿轮至少c个齿
→k * b ≥ c且k * a ≥ c
目标：最小化总齿数 = k(a + b)*
→ 即找最小的正整数k，使得：
k≥⌈c/a⌉且k≥⌈c/b⌉
→ 所以：
k=max(⌈c/a⌉,⌈c/b⌉)
但注意！这里a和b是原始输入值，我们需要先约分！
🔑 关键：必须用最简比例！
因为如果a和b有公因数，直接用会导致k不是最小。
例如：a=4, b=8
- 原始比例：A:B = 8:4 = 2:1
- 最简比例：
a'=1, b'=2（因为 gcd(4,8)=4） - 所以 A 齿数 =
k*2, B 齿数 =k*1 - 约束：
2k ≥ c,k ≥ c→k ≥ max(ceil(c/2), ceil(c/1)) = c - 若
c=5→k=5→ A=10, B=5 → 总=15（符合样例）
所以第一步：将a:b化为最简整数比
代码简析
long long gcd(long long a, long long b){ return b ? gcd(b, a % b) : a; }- 实现欧几里得算法，求最大公约数（GCD）
int main(){ int T; long long a, b, c, t; cin >> T;- 读入测试数据组数
T a, b, c：题目输入t：临时变量（用于存 gcd 或 min）
while(T--){ cin >> a >> b >> c;- 读入每组数据
🔥 第一步：约分比例
t = gcd(a, b); a /= t; b /= t;- 将
a : b化为最简整数比 - 例如：
a=4, b=8→gcd=4→a=1, b=2 - 此时，齿轮齿数比例为 B:A = a:b（注意方向！）
💡 回顾：A 转
a圈 → B 转b圈
→ A 齿数 / B 齿数 = b / a
→ 所以 A 齿数 =k * b，B 齿数 =k * a
✅ 约分后，a和b互质，此时k取最小值即可保证齿数最小。
🔥 第二步：计算最小缩放因子k
t = min(a, b);- 这里
t被重用，表示min(a, b)（约分后的）
❓ 为什么取
min(a, b)？
看约束：
- A 齿数 =
k * b ≥ c→k ≥ ceil(c / b) - B 齿数 =
k * a ≥ c→k ≥ ceil(c / a)
所以k = max( ceil(c/a), ceil(c/b) )
但代码却写：
if(c % t == 0) c /= t; else c = c / t + 1;这看起来像是在算ceil(c / t)，其中t = min(a, b)
这是错误的吗？
🚨 重大疑问：为什么用min(a, b)而不是分别计算？
我们用样例验证：
样例 1：a=2, b=3, c=4
- gcd(2,3)=1 → a=2, b=3
- t = min(2,3) = 2
- c=4,
4 % 2 == 0→ c = 4/2 = 2 - 输出：
a*c + b*c = (2+3)*2 = 10✅
但按正确逻辑：
- A 齿数 =
k * b = 3k ≥ 4→ k ≥ 2（因为 3×1=3<4） - B 齿数 =
k * a = 2k ≥ 4→ k ≥ 2 - k = 2 → 总齿数 = 3×2 + 2×2 = 10 ✅
这里min(a,b)=2，ceil(4/2)=2，而ceil(4/3)=2，所以max=2，和ceil(c / min(a,b))相等。
样例 2：a=4, b=8, c=5
- gcd=4 → a=1, b=2
- t = min(1,2)=1
- c=5,
5%1==0→ c=5 - 输出：
(1+2)*5=15✅
正确逻辑：
- A 齿数 = 2k ≥5 → k≥3（2×2=4<5）
- B 齿数 = 1k ≥5 → k≥5
- k = max(3,5)=5 → 总=2×5+1×5=15 ✅
但min(a,b)=1，ceil(5/1)=5，而ceil(5/2)=3，max=5，等于ceil(c / min(a,b))
样例 3：a=5, b=2, c=8
- gcd=1 → a=5, b=2
- t = min(5,2)=2
- c=8,
8%2==0→ c=4 - 输出：
(5+2)*4=28✅
正确逻辑：
- A 齿数 = 2k ≥8 → k≥4
- B 齿数 = 5k ≥8 → k≥2（5×1=5<8, 5×2=10≥8）
- k = max(4,2)=4 → 总=2×4+5×4=28 ✅
而min(a,b)=2，ceil(8/2)=4，ceil(8/5)=2，max=4=ceil(c / min(a,b))
✅ 发现规律！
因为：
k ≥ ceil(c / a)且k ≥ ceil(c / b)- 而
ceil(c / x)是x的减函数（x 越大，值越小） - 所以
max(ceil(c/a), ceil(c/b)) = ceil(c / min(a, b))
✅ 证明：
- 设
m = min(a, b)，则m ≤ a且m ≤ b - 所以
c/m ≥ c/a且c/m ≥ c/b - 因此
ceil(c/m) ≥ ceil(c/a)且ceil(c/m) ≥ ceil(c/b) - 又因为
m是a或b之一，所以ceil(c/m)就是两者中的较大者
回到代码
t = min(a, b); if(c % t == 0) c /= t; else c = c / t + 1;- 这就是在计算
k = ceil(c / t) = ceil(c / min(a, b)) - 然后
c被重用为k
cout << a * c + b * c << endl;- 总齿数 =
k * a + k * b = k * (a + b) - 注意：这里
a和b是约分后的值 - A 齿数 =
k * b，B 齿数 =k * a，总和 =k*(a + b)✅
⚠️ 虽然变量名
a, b容易让人混淆方向，但因为加法交换律，a*c + b*c = (a+b)*c，结果正确。
✅ 总结：代码逻辑链
- 读入
a, b, c - 约分
a : b为最简比（除以 gcd） - 计算最小缩放因子
k = ceil(c / min(a, b))- 利用数学性质：
max(ceil(c/a), ceil(c/b)) = ceil(c / min(a,b))
- 利用数学性质：
- 总齿数 = k × (a + b)
- 输出
🧪 再验证样例
| 输入 | 约分后 (a,b) | min | k = ceil(c/min) | 总齿数 |
|---|---|---|---|---|
| 2 3 4 | (2,3) | 2 | ceil(4/2)=2 | (2+3)×2=10 |
| 4 8 5 | (1,2) | 1 | ceil(5/1)=5 | (1+2)×5=15 |
| 5 2 8 | (5,2) | 2 | ceil(8/2)=4 | (5+2)×4=28 |
全部匹配！
✅ 最终结论
这段代码关键之处：
- 利用齿轮转速与齿数反比建立比例关系
- 通过约分得到最简整数比
- 利用数学恒等式将双上限约束简化为单上限
- 用整数除法高效计算上取整
是典型的“数学建模 + 数论优化”竞赛题解法
