Pallo

#include <bits/stdc++.h>

typedef long long ll;

#define M 1000000007
#define N (1 << 18)

using namespace std;

ll gcd(ll a, ll b) {
   if (b == 0)
   return a;
   return gcd(b, a % b);
}

ll cor(ll n, ll m, ll k) {
    pair<ll, ll> pos = {1, 1};
    pair<int, int> dir = {1, 1};
 
    ll ans = 0;
 
    for (ll t = 0; t < k;) {
        //pos = {pos.first + dir.first, pos.second + dir.second};
        
        int rightdst = m - pos.first;
        int leftdst = pos.first - 1;
 
        int updst = pos.second - 1;
        int downdst = n - pos.second;
 
        int xdst = dir.first == 1 ? rightdst : leftdst;
        int ydst = dir.second == 1 ? downdst : updst;
 
        int travel = min(xdst, ydst);
 
        t += travel;
 
        if (t > k) break;
 
        pos = {pos.first + travel * dir.first, pos.second + travel * dir.second};
 
        bool hit = 0;
        if (pos.first == m || pos.first == 1) {
            hit = 1;
            dir.first *= -1;
        }
        if (pos.second == n || pos.second == 1) {
            hit = 1;
            dir.second *= -1;
        }
        ans += hit;
 
        if (pos.first == 1 && pos.second == 1) {
            ll runs = k / t;
            ans *= runs;
            k -= (runs - 1) * t;
        }
    }
 
    return ans;
}

ll fast(ll n, ll m, ll k) {
    n--;
    m--;
    ll vert = k / n;
    ll hor = k / m;
    ll corner = k / (n * m / gcd(n, m));

    return vert + hor - corner;
}

void test_case() {
    ll n, m, k;
    cin >> n >> m >> k;

    ll ans = fast(n, m, k);

    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        test_case();
        cout << "\n";
    }

    /*while (true) {
        ll n = rand() % 5 + 2;
        ll m = rand() % 5 + 2;
        ll k = rand() % 5 + 1;

        ll ans = cor(n, m, k);
        ll out = fast(n, m, k);

        if (ans != out) {
            cout << "FAIL" << endl;
            cout << "GOT " << out << " WAS " << ans << endl;
            cout << n << ", " << m << ", " << k << endl;
            break;
        }
    }*/

    return 0;
}

/*for (ll t = 0; t < k;) {
        
        int rightdst = m - pos.first;
        int leftdst = pos.first - 1;

        int updst = pos.second - 1;
        int downdst = n - pos.second;

        int xdst = dir.first == 1 ? rightdst : leftdst;
        int ydst = dir.second == 1 ? downdst : updst;

        int travel = min(xdst, ydst);

        t += travel;

        if (t > k) break;

        pos = {pos.first + travel * dir.first, pos.second + travel * dir.second};

        bool hit = 0;
        if (pos.first == m || pos.first == 1) {
            hit = 1;
            dir.first *= -1;
        }
        if (pos.second == n || pos.second == 1) {
            hit = 1;
            dir.second *= -1;
        }
        ans += hit;

        if (pos.first == 1 && pos.second == 1) {
            ll runs = k / t;
            ans *= runs;
            k -= (runs - 1) * t;
        }
    }*/

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED