AtCoder Grand Contest 001 B - Mysterious Light

問題

agc001.contest.atcoder.jp

解法

こういうの, 直感的に gcd もしくはその考え方を使うような気がします。と考えて適当にやると解けそうです(本番そんな感じで適当に書いたら AC してびっくりしました)

真面目な話をすると, 2 回光が反射したのちは, 必ず残った形が平行四辺形になります。

平行四辺形の長さを a, b (a > b) とすると, 2 * b * floor(a/b) だけ光が進んで, 残りの平行四辺形が b, a%b となります。

このように平行四辺形の長さを変えていくのは gcd を求める過程と同じなので, 計算量は O(log N) です。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, X;
    cin >> N >> X;
    ll a = X, b = N-X;
    if (a < b) swap(a, b);
    ll ans = N;
    while (b) {
        ll k = a/b;
        ans += (2*k)*b;
        ll c = a%b;
        a = b, b = c;
    }
    ans -= a;
    cout << ans << endl;
    return 0;
}