SRM 537 Div2 Medium KingXNewCurrency

問題

アヒルの国では整数A, Bのコインが使われ,A*p, B*qのお金を支払うことが出来る.王様は新しい料金システムを導入しようとX, Yのコインを使おうと思っている.新しいコインの条件はA*p, B*qの全ての価格を表現できること.
今A, B, Xがわかっている時条件を満たすYの個数を求めよ.Yが無限にある時は-1を返せ.

解答

A, Bの組み合わせで表される全ての値をX, Yで表すには,A, BがX, Yで表せれることが条件.XだけでA, Bが表せれる時,Yは無限にある.またそうではない場合有限.範囲が200以下なので全てのYについて考え,A, Bを表現できるのかチェックする.

class KingXNewCurrency
{
public:
  int howMany(int A, int B, int X)
    {
      int i, j;
      for(i = X; i < A; i += X) ;
      for(j = X; j < B; j += X) ;
      if (i == A && j == B) return -1;
      if (X == 1) return -1;
      int res = 1;
      for(int Y = 2; min(X, Y) <= min(A, B) && Y <= max(A, B); Y++){
        if (X == Y) continue;
        bool validA = false;
        bool validB = false;;
        for(i = 0; i <= max(A, B); i += X){
          for(j = 0; j <= max(A, B); j += Y){
            if ((i+j) == A) validA = true;
            if ((i+j) == B) validB = true;
          }
        }
        if (validA && validB){
          res++;
          continue;
        }
      }
      return res;
    }
};