Weird Subtraction Process [Educational Codeforces Round 39 B]

http://codeforces.com/contest/946/problem/B

数A,Bが最初与えられ、以下のルールでA,Bを更新していく。
1. A=0 or B=0 の場合は終了。そうでないなら操作2へ
2. 2B≦Aならば、A=A-2Bとして、操作1へ。そうでないなら操作3へ
3. 2A≦Bならば、B=B-2Aとして、操作1へ。そうでないなら終了
最終的なA,Bを答えよ。

解法

http://codeforces.com/contest/946/submission/36152680

シミュレーションする。
概ねそのままシミュレートすればいいのだが、そのままやるとTLE。
そのため、枝刈りをして通そう。
例えば、A=100でB=1ならば、操作2が繰り返し行われて無駄になる。
そのため、A=A-2Bではなく、A%=2Bとして、繰り返しの無駄を無くす。
操作3も同様にB%=2AとしてやるとAC

ll A, B;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B;
    while (1) {
        if (A == 0 or B == 0) break;
        else if (A >= 2 * B) A %= 2 * B;
        else if (B >= 2 * A) B %= 2 * A;
        else break;
    }
    printf("%lld %lld\n", A, B);
}