POJ 2499 Binary Tree

問題

(1, 1)という値を根に持つ完全二分木があり、各ノード(仮に(a, b)とする)からは左に(a + b, b)という値を持つ子、右に(a, a + b)という値を持つ子が伸びている。
(x, y)というノードから親を辿りながら根まで行くときに左側に移動する回数と右側に移動する回数をそれぞれ答えよ。

やり方

xの方が大きいとしておく。まず右側に動くことになるが、この時連続して回動くことができる。移動後のノードは(x % y, y)になり今度は左側に動くことになる。これもいま右側に動いたのとやることは一緒。これをどちらかが0になるまで繰り返す。yの方が大きいときでもやることは同じ。
これは結局ユークリッドの互除法をやっていることになる。ただし、この方法では最後に(1,0)か(0,1)という状態で終わってしまうので(1,1)にするためには最後に移動した方向の回数を一つ引かなくてなならない。

最大公約数を求める処理の回数を数えているわけなので、これを繰り返すと(1, 1)にいたるということは(x, y)の最大公約数は(1, 1)の最大公約数に同じということになる。ゆえにx,yは互いに素ということが根にいたるための条件。

以下ソース。

int main(int argc, char **argv){
  int t;
  scanf("%d", &t);
  for(int i = 1; i <= t; i++){
    int a, b, l = 0, r = 0;
    scanf("%d %d", &a, &b);

    int idx = 0;
    while(a * b){
      if(idx++ % 2 == 0){
	l += a / b;
	a %= b;
	if(a == 0) l--;
      }else{
	r += b / a;
	b %= a;
	if(b == 0) r--;
      }
    }
    printf("Scenario #%d:\n", i);
    printf("%d %d\n\n", l, r);
  }
  return 0;
}