[AOJ] No. 0361 電線

2019年12月17日

問題

方針

まず初めに、重複する点を許すと、縦方向の電線と \( x + 1 \) 回交わり、横方向の電線と \( y + 1 \) 回交わることになります。また、必ず端点で \( 2 \) 回縦方向と横方向の電線に交わるので、その分除外しなければなりません。端点以外で重複する点を考えます。ここで、次の直線を考えます。

\[ Y = \dfrac{y}{2x}X \ ( 0 < X <2x \wedge 0 < Y < y)\]

この直線は、タイルの対角線を表しています。また、\( X \) は \( 2 \) しか取らないので、次の方程式を考えます。

\[xY = yX \ ( 0 < X <x \wedge 0 < Y < y)\]

上式を満たす自然数 \( (X, Y) \) が端点以外で重複する点となります。ここで、\( g = gcd(x, y) \) とし、\( x = pg , y = qg\) とします。 \( p , q \) は互いに素です。これを上式に代入すると、

\[pY = qX\]

となります。この解は、整数 \( k \) を用いて、\( (X, Y) = (kp, kq)\) となります。したがって、\( k \) の個数が求まれば良いことが分かります。\( 0 < kp < x \) より、\( 0 < k < g \) となり、\( 0 < kq < y\) より、\( 0 < k < g \) となります。なので、\( 1 \leq k \leq g – 1 \) となり、除外する点は、\( g – 1 \) となります。

以上より、求める答えは、\( (x + 1) + (y + 1) – 2 – (g – 1) = x + y + 1 – g \) となります。

コード

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

ll gcd(ll m, ll n) {
  if (n == 0) return m;
  else return gcd(n, m % n);
}

int main() {
    ll x, y;
    cin >> x >> y;
    cout << x + y - gcd(x, y) + 1 << "\n";
    return 0;
}