Codeforces 217B Blackboard Fibonacci

問題

黒板に二行に数字を書く。
最初、上の行に0, 下の行に1を書いた後で次の操作を繰り返す。

• Tの操作 上の行の数字 := 上の行の数字 + 下の行の数字　と書き換える。
• Bの操作 下の行の数字 := 上の行の数字 + 下の行の数字　と書き換える。

これをn回行った結果、最後にrの数字が書かれた。
操作はTBTBTB...と行うはずであったが、何度か間違えて、連続して同じ操作を行った。
間違った回数の最小値および、そのときの操作の列をどれか一つ出力せよ。
（間違いの回数は、同じ操作を連続して行った回数 + 最初がTならさらに1回）

制約条件

n, r≦10^6

方針

最後の状態は(r, x)または(x, r).
最後の状態を一通り決めると、直前の状態は一意に定まるので、
最後の状態を2*r通り全通り決め付けて、最初の状態(0, 1)に戻るかを見ればよい。
一つの状態を(0, 1)に戻すには、互除法と同じ計算量のO(log r)かかるので、全体でO(rlog r)で求まる。

計算できたら解を復元すればいい。
なんか書き方によってはコーナーケースができるっぽいので注意する必要がある。

ソースコード

int n, r;
int calc(int t, int b){
	int res = 0, step = 0;
	while(t > 0 && b > 0){
		if(t <= b){
			res += b / t - 1;
			step += b / t;
			b %= t;
		}
		else{
			res += t / b - 1;
			step += t / b;
			t %= b;
		}
	}
	if(max(t, b) != 1 || min(t, b) != 0  || n != step) return inf;
	if(t == 1) res--;
	return res;
}
int main(){
	cin >> n >> r;
	int best = inf, t = -1, b = -1;
	string ans;
	
	if(n == 1 && r == 1){
		cout << "0\nT"<< endl;
		return 0;
	}
	
	rep(i, r){
		int tmp = calc(i, r);
		if(tmp < best) best = tmp, t = i, b = r;
		tmp = calc(r, i);
		if(tmp < best) best = tmp, t = r, b = i;
	}
	if(best == inf){
		cout << "IMPOSSIBLE" << endl;
		return 0;
	}
	while(t > 0 && b > 0){
		if(t < b){
			rep(i, b / t) ans += 'B';
			b %= t;
		}
		else{
			rep(i, t / b) ans += 'T';
			t %= b;
		}
	}
	reverse(all(ans));
	if(t == 1) ans[0] = 'T';
	cout << best << endl;
	cout << ans << endl;
	
	return 0;
}