Codeforces #200 Div1. A. Rational Resistance

CF200は本番参加。A,Cは無事解けたものの、Bはpretest通過後WAして微妙な順位に終わった。
http://codeforces.com/contest/343/problem/A

問題

電気回路において、抵抗を直列に抵抗値はその合計に、並列につなげると抵抗値は調和平均になる。
ある回路の抵抗値が有理数A/Bの形で与えられる。
抵抗値1の抵抗を複数個使って全体の抵抗値をA/Bにするとき、必要な抵抗の数を最少化せよ。

解法

再帰的に行う。
B=1ならA個直列、A=1ならB個並列に抵抗値1の抵抗を並べればよい。
それ以外の場合、A>BならA/B個分の抵抗値1の抵抗と、抵抗値(A%B)/Bを実現する抵抗を直列につなげばよいので、抵抗値(A%B)/Bを実現する抵抗の数を再帰的に求めてA/Bと足せばよい。
A

ll gcd(ll a, ll b) { return (b==0)?a:gcd(b,a%b);}

ll dodo(ll A,ll B) {
	ll g=gcd(A,B);
	A /= g;
	B /= g;
	if(B==1) return A;
	if(A>B) return A/B + dodo(A%B,B);
	if(A==1) return B;
	return B/A+dodo(A,B%A);
}


void solve() {
	int f,r,i,j,k,l, x,y;
	ll A,B;
	
	cin>>A>>B;
	cout << dodo(A,B) << endl;
}

まとめ

最大公約数って今までまじめに書いてたけど、g++は(STLは？)__gcdって関数があるのね。