TopCoder SRM247 Div2 500Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。それでは、問題について説明する。

互いに素な整数から0と1の間の既約分数を作成することができる(つまり無限に分数が存在していることを示している)。それらを表す時は、通常次のように表す。

1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5 1/6 5/6 1/7 ...

2/4というのは数列中にはないが、これは1/2に約分できるからである。既約分数が与えられたときに、上のような順序の数列の何番目に現れるかということが知りたい。例えば、1/3であれば2というインデックスが知りたい。FracCountという分子と分母の互いに素な整数が与えられたときに、その2数から作られる分数が何番目に現れるかを返すメソッドを作成せよ。

私の解答はこちら。

public class FracCount {
 public int position(int numerator, int denominator) {
  int idx = 0;
  for( int i=2 ; i<=denominator ; i++ ){
   for( int j=1 ; j<i ; j++ ){
    // 最大公約数が1であれば、約分不可なので、初登場の分数になる
    if( gcd(i,j) == 1 ) idx++;
    // 求めている分数が現れた時点で処理は終了
    if( i==denominator && j==numerator)break;
   }
  }
  return idx;
 }
 private int gcd(int a, int b){
     return b == 0 ? a : gcd(b, a % b);
 }
}

得点は419.40/500。500点問題にしては、全体の解答者が50%と高めだったので解いてみたところ、予想よりすんなりと解けました。breakに関連した処理を入れ忘れて再提出したのですけどね。