TopCoder SRM373 Div2 250Pts

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

X、Y、Pという3つの正の整数が与えられる。a、bを正の整数としてa*X+b*YがPで割り切れるとき、a+bを最小にするaとbの組合せを求め、その値を求めよ。

私の解答はこちら。

public class TheEquation {

 public int leastSum(int X, int Y, int P) {
  int min = Integer.MAX_VALUE;
  for( int i=1 ; i<=2*P ; i++ ){
   for( int j=1 ; j<=2*P ; j++ ){
    if( (i*X+j*Y) % P == 0 ){
     min = Math.min(min, i+j);
    }
   }
  }
  return min;
 }

}

得点は243.63/250、1回のsubmitでシステムテストクリア。当日の正解率は約82%。ヒントにより探索範囲が分かるので、簡単でした。解答が2*P以下になるということ(P*X+P*YがPで割り切れるから)なので、全探索でゴリ押し。