SRM 537 250pt : KingXNewCurrency
問題概要
A*p + B*q (p, q ≧ 0)の集合をX*p + Y*qが含むようにしたい。そのようなA,B,X(<200)が与えられるので適切なYの個数を求める問題。無数に存在する場合は指摘する。
解法
XがA,Bの約数なら無数に存在する。それ以外の時、X*p+Y*qによってA、Bが少なくとも作れなければならない。また、A、BがつくれたらA*p + B*qは自然に作ることができる。なので、A、Bがつくれるかどうかだけを見れば良い。
acceptされたコード
#include <vector> #include <algorithm> using namespace std; struct KingXNewCurrency { int howMany(int A, int B, int X) { if(__gcd(A, B) % X == 0){ return -1; } int ans = 0; for(int Y=1; Y<=400; Y++){ if(can_make(A, X, Y) && can_make(B, X, Y)){ ans++; } } return ans; } bool can_make(int A, int X, int Y){ for(int i=0; i*X<=A; i++){ for(int j=0; j*Y<=A; j++){ if(i*X + j*Y == A){ return true; } } } return false; } };