Pallo

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    long n, m, k;
    cin >> n >> m >> k;
    if (n > m) swap(n, m);
    long K = (m - n) / (n - 1);
    long x = __gcd(m - n, n - 1);
    long T = (n - 1) / x;
    long vs = K + 1 + (T - 1) + ((m - n) % (n - 1) + (m - n) * (T - 1)) / (n - 1);
    long ans = k / (vs * (n - 1)) * (vs + (T - 1));
    k %= vs * (n - 1);
    if (k <= (K + 1) * (n - 1)) {
      ans += k / (n - 1);
      k = 0;
    } else {
      k -= (K + 1) * (n - 1);
      ans += K + 1;
    }
    if (k > 0) {
      auto check = [&](long i) {
        if (i < 0) return 0l;
        return (i + 1) * (n - 1)
             + ((m - n) % (n - 1) + (m - n) * (i + 1)) / (n - 1) * (n - 1);
      };
      long i = -1;
      for (long bit = 1l << __lg(T); bit; bit /= 2) {
        if (i + bit < T - 1 && check(i + bit) < k) {
          i += bit;
        }
      }
      assert(k > check(i) && (i == T - 2 || k <= check(i + 1)));
      k -= check(i);
      ans += (i + 1) * 2;
      ans += ((m - n) % (n - 1) + (m - n) * (i + 1)) / (n - 1);
      i++;
      if (i < T - 1) {
        long rem = ((m - n) % (n - 1) + i * (m - n)) % (n - 1);
        if (k >= rem) {
          k -= rem;
          ans++;
          if (k >= n - 1 - rem) {
            k -= n - 1 - rem;
            ans++;
            rem += m - n;
            long f = min(k / (n - 1), rem / (n - 1));
            ans += f;
            k -= f * (n - 1);
            assert(k >= 0);
          }
        }
      }
    }
    cout << ans << endl;
  }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED