Sicily 1422 Table Tennis：最小公倍數與反射建模

問題描述

矩形桌球桌 ABCD，邊長 m（寬）和 n（長），m < n。球從左下角 A 以 45° 角射出，邊界完全彈性反射。求球首先落入哪個角袋（A/B/C/D）及撞擊邊緣總次數。多組測試數據。

幾何建模：鏡像展開法

將反射路徑等效為直線：每次撞擊邊界視為進入一個鏡像桌面。球以 45° 運動，即 x、y 方向速度分量相等。球在時間 t 位置為 (t, t)（模邊長）。

球落入角袋當且當 t 同時是 m 和 n 的倍數，即 t = LCM(m, n)。此時：

• 水平方向經過 LCM/m 個桌面寬度 → 撞擊垂直邊緣 LCM/m - 1 次（扣除落袋那次）。
• 垂直方向經過 LCM/n 個桌面長度 → 撞擊水平邊緣 LCM/n - 1 次。

判斷落袋角落

設 hx = LCM/m - 1（垂直邊撞擊數），hy = LCM/n - 1（水平邊撞擊數）。
根據奇偶性判斷最終所在鏡像桌面的角落：

總撞擊次數 = hx + hy。

代碼實現

#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b) {
    while (b) { a %= b; swap(a, b); }
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long m, n;
    while (cin >> m >> n) {
        long long lcm = m / gcd(m, n) * n;  // 防溢出寫法
        long long hx = lcm / m - 1;  // 撞擊垂直邊（左右）
        long long hy = lcm / n - 1;  // 撞擊水平邊（上下）
        char pocket;
        if (hx & 1) {
            pocket = (hy & 1) ? 'A' : 'D';
        } else {
            pocket = (hy & 1) ? 'B' : 'C';
        }
        cout << pocket << ' ' << hx + hy << '\n';
    }
    return 0;
}

樣例驗證

輸入 6 10：
gcd=2, lcm=30
hx = 30/6 - 1 = 4（偶），hy = 30/10 - 1 = 2（偶） → C，總撞擊 6。
輸出 C 6，與樣例一致。

複雜度

每組 O(log min(m,n))，極快。注意 m,n 為 32 位有符號整數，lcm 可能超過 32 位，需用 long long。