Codeforces 134 B. Pairs of Numbers

問題

数のペア(a,b)にを、(a+b,b)または(a,a+b)にかえる操作をすることができる。
(1,1)から始めて、ペアのどちらかの数がnになるのに必要な操作の最小回数を求めよ。

制約条件

n≦10^6

方針

逆からやる。
(a,b)の前の形はa>bなら(a-b,b)、a<bなら(a,b-a)と一通りに定まる。

最後は(a,n)の形になっているはずなので、aの値を1からnまで全部試す。
ただし、gcd(a,n)=1でないと(1,1)まで戻れないので、gcd(a,n)=1であるaだけを全部試す。

再帰でやったら手元ではスタックオーバーフローで落ちた。
ループで書く必要がある（？）

ソースコード

void run()
{
	int n; cin>>n;
	int ans=inf;
	for(int i=1;i<n;i++)if(__gcd(i,n)==1){
		int t=0,a=i,b=n;
		while(a!=b){
			if(a>b)a=a-b;
			else b=b-a;
			t++;
		}
		ans=min(ans,t);
	}
	cout<<(n==1?0:ans)<<endl;
}