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;
	}

};