AOJ VolumeACPC2015Day1 D : Checkered Pattern

問題

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2015Day1&pid=D

解法

適当に実験すると答えがわかります。

自明っぽいところから攻めて行きます。
まず, g = gcd(h, w) とすると, (h/g, w/g) の長方形を g 回同じように繰り返しているだけだとわかります。なので, ここからは h = h/g, w = w/g としましょう。ここで,

• h+w が偶数のとき
  • 長方形の左上のマスの色は 白→黒→白…　と交互に入れ替わります。
• h+w が奇数のとき
  • 長方形の左上のマスの色は 白→白→白…　と一定です。

なので, h+w が偶数の場合には (h, w) における 白と黒の長さの比が得られれば良いです。h+w が奇数の場合は面倒そうに思えますが, h+w が奇数の場合は h と w のどちらかは偶数です。h が偶数であるとすると, 0 ～ h/2 の部分と h/2 ～ h の部分には対称性があるので, 長さの比は必ず 1:1 です。よって, 答えは 1:1 になります。

後は h+w が偶数のときなんですが, これは実験したら 比が (h*w+1)/2 : (h*w-1)/2 になることがわかりました。ﾅﾝﾃﾞﾅﾝﾃﾞｼｮｳﾈ

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        ll h, w;
        cin >> h >> w;
        ll g = __gcd(h, w);
        h /= g;
        w /= g;
        if ((h+w)%2) {
            cout <<  "1 1" << endl;
        } else {
            ll mul = h*w;
            cout << (mul+1)/2 << " " << (mul-1)/2 << endl;
        }
    }
    return 0;
}