# 官方题解｜欢乐赛#38 T6

T6

看似比较麻烦，我们不妨转化一下思路：在某一个时间段 $t$ 上看到的所有仙女棒是前面第 $t-m \sim t$ 时间段上释放的所有仙女棒。那么问题就转化成了：找一个时间段，长为 $m+1$，使得这个时间段上释放的仙女棒最多。

如果我们要让一个仙女棒在一个时间段上释放的次数最多，根据贪心的思想，显然区间左端点应该在这个仙女棒刚刚释放的时候，假设这个仙女棒释放间隔是 $a$，那么这个时间段上仙女棒会释放 $\left\lfloor \frac{m}{a} \right\rfloor + 1$ 次。

同理，两个仙女棒也是如此。我们希望区间左端点选在两个仙女棒同时释放的时刻。问题在于这两个仙女棒在同同时释放的情况下吗？如果两个仙女棒是倍数关系，那么必然存在；如果不是倍数关系，那么两个数的最小公倍数对应的次数时刻是两个仙女棒同时释放的时刻。因此两个仙女棒一定存在同时释放的情况。

因此两个仙女棒总的释放次数就是 $\left\lfloor \frac{m}{a} \right\rfloor + \left\lfloor \frac{m}{b} \right\rfloor + 2$。

#include <bits/stdc++.h>
 #define int long long
using namespace std;
   
const int N = 200010;
int a[N], n, m, k;
 
void solve(){
    cin >> n >> m >> k;
    cout << k / n + k / m + 2 << endl;
}
 
signed main(){
    int tt = 1;
    cin >> tt;
    while(tt -- ){
        solve();
    }
    return 0;
}