電線 [パソコン甲子園2017 予選 E]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0361?year=2017

前提知識

• 最大公約数(GCD)

考察過程

1. 電線とパネルの継ぎ目の交点を全て求めれば答えが出そう
2. でも解法としてかなり大変に思える
3. なにかに着目して、問題をもっと単純に考えられないか
4. パネルの横線について考えてみると、1つの横線について必ず交点が1つある
5. 縦線も同様
6. よって、交点は(x+1)+(y+1)となりそう
7. でも一部交点を共有している部分がある
8. 丁度交点となっている部分は座標が整数なので、xもyも丁度割り切れる座標である
9. それは最大公約数であるため、共有部分の個数はgcd(x,y)+1個で、これを引くと答え

解説

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0361/review/3136449/hamayanhamayan/C++14

最大公約数はよく使われるので、ライブラリ化しておこう。
最大公約数はユークリッドの互除法で高速に求める方法が知られている。
縦線横線ともにただ1つの交点を持つので、交点は(x+1)+(y+1)
しかし、共有している交点がgcd(x,y)+1個あるので、それを引いて答え。
急にgcdが出てきた感じがするが、グリッドで左上から右下へ直線を引いて考える問題はgcdがよく出てくるという知見がある。

int x, y;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> x >> y;

    int ans = (x + 1) + (y + 1) - (gcd(x,y) + 1);
    cout << ans << endl;
}