SRM537 Div1 Easy - KingXNewCurrency

問題

自然数a, b, xが与えられる
任意の(p,q)に対して pa+qb = rx+sy を満たす(r,s)が存在するような(x,y)の組の個数を求めよ
(ただしp, q, r, sは非負整数でyは自然数)
答えが無限に存在する場合は-1を返せ

1 <= a, b, x <= 200
a ≠ b

解法

aもbもxの倍数の場合、yの値によらず条件が成り立つからreturn -1

①任意の(p,q)に対して pa+qb = rx+sy を満たす(r,s)が存在する
という条件は
②任意のpに対して pa = rx+sy を満たす(r,s)が存在し、かつ、任意のpに対して pb = rx+sy を満たす(r,s)が存在する
と同値だから、yを200まで全部試し、aもbもxとyの組み合わせで作れる場合のみ答えを+1していけばいい

class KingXNewCurrency {
public:
	bool ok(int a, int x, int y) {
		rep(i,222) if (a>=x*i && (a-x*i)%y==0) return 1;
		return 0;
	}

	int howMany(int a, int b, int x) {
		if (a%x==0 && b%x==0) return -1;
		int res = 0;
		reps(y,1,222) if (ok(a,x,y) && ok(b,x,y)) res++;
		return res;
	}
};