考察
1. 幾何問題として考えるにはむずすぎる気がする
2. 再帰的に解けるのでは？？
3. （コンテスト後にTwitterを見ると、強い人は「ユークリッド系問題かな？」と思うみたいです）
4. （実際そうだからすごい）
5. 再帰的に解くのはいいのだけれど、引数はどうしようか
6. 今回は斜めに動いているが、2直線上でしか動いていない
7. つまり、直線bcをx軸、直線baをy軸と見立てて考えみる
8. あと、もう一つ大切なことが、光の線が増えるたびに光の線が移動できる範囲が狭まる
9. 範囲が狭まる -> 再帰的に解けそう
10. ここまでくればもう一歩
11. 問題文の図を見ると、最初の2回の光の遷移後は、平行四辺形になっている
12. その後2回の遷移でまた平行四辺形。そのまた2回の遷移で平行四辺形。。。
13. 平行四辺形について再帰的に求めればいい！
14. 以下の様な再帰を考えれば良い
rec(int x, int y) : 平行四辺形のx軸方向の長さx,y軸方向の長さyで、これ以降の遷移での光の軌跡の長さ
x < y : return rec(x, y - x) + x * 2
x > y : return rec(x - y, y) + y * 2
x = y : return x
15. 実際、これで作るとTLEする
16. 原因は、x <<< y（xよりyが凄い大きいってこと） の時なので、その場合は遷移をまとめてやる必要がある
実装
http://agc001.contest.atcoder.jp/submissions/808778
typedef long long ll; ll N, X; //----------------------------------------------------------------- ll solve(ll x, ll y) { if (x == 0 || y == 0) return 0; if (x < y && y % x == 0) return (y / x) * x * 2 - x; if (y < x && x % y == 0) return (x / y) * y * 2 - y; if (x < y) return solve(x, y - (y / x) * x) + (y / x) * x * 2; else if (x > y) return solve(x - (x / y) * y, y) + (x / y) * y * 2; else return x; } //----------------------------------------------------------------- int main() { cin >> N >> X; ll ans = solve(X, N - X) + N; cout << ans << endl; }
