AtCoder Grand Contest 001 B - Mysterious Light
解法
こういうの, 直感的に 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; }