AGC001 B問題 Mysterious Light

問題

agc001.contest.atcoder.jp

解説

解法の方針はユークリッドの互除法です。 なぜこの問題を見てユークリッドの互除法が思いつくのかをまず解説していきます。

ユークリッドの互除法を幾何的に説明したサイトがあったので紹介します。 math-arithmetic.blogspot.jp

x, yの最大公約数をユークリッドの互除法で求める操作を図で表すとすると「縦の長さx, 横の長さyの長方形をできる限り大きな正方形で埋めていき全て埋まった時の最小の一辺の正方形の長さが最大公約数」になります。

ではなぜこの考えが問題に関係あるのかを次に説明していきます。 まず最初の光の航路(反射するまで)と底辺が対辺になる平行四辺形に注目してください(下図)

さらに下図を見てみてください

この問題は光の航路と三角形の辺で構成される平行四辺形を全ての辺が同じ長さのできる限り大きな平行四辺形で埋めていっているだけなのです。 また細かく見ると正三角形で埋められています。 以上の点からユークリッドの互除法の発想が浮かんでくるかと思います。
次に実際にユークリッドの互除法を用いてこの問題を解いていきます。

下図の赤い線に注目してください。

図の中に光の航路で囲まれている大きい正三角形１つと小さい正三角形２つがあります。この赤い線の長さはそれぞれの三角形の一辺の長さの和になります。 では長さはいくつになるでしょうか。ここで用いるのが先ほどの最大公約数です。図の中で最大公約数は正方形で埋めた時の最小の正方形の長さです。(ここでは平行四辺形の長さ)
下図の緑線に注目してください。
緑の線と赤の線の和は (N-x) + x になります。それは横にxだけ縦にN-xだけ移動しているからです。 そして緑の線の長さは前述した通りgcd(N-x, x)になるので赤い線の長さは N-gcd(N-x, x) になります。 よってこれは一辺の長さの総和なので求めるのは3倍した3*(N-gcd(N-x, x))

※解説ではgcd(N,x)ですがgcd(N-x, x)でも大丈夫です。

コード

#include <iostream>
#define ll long long
using namespace std;

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

int main(void){
    ll n, x;
    cin >> n >> x;
    ll gc = gcd(n-x, x);
    cout << 3*(n-gc) << endl;
    return 0;
}