SRM 537 div1 easy: KingXNewCurrency

問題

TopCoder Statistics - Problem Statement

解法

求める条件は,
「任意の p, q(>= 0) に対して, ある r, s(>= 0) が存在して, p*A + q*B = r*X+s*Y」が成り立つことですが, この条件と
「"ある r, s が存在して, A = r*X+s*Y" かつ "ある r, s が存在して B = r*X+s*Y"」は同値です。

(⇒)
p=1, q=0 のセットと, p=0, q=1 のセットを考えれば明らか。
(⇐)
A = ra*X + sa*Y, B = rb*X + sb*Y が成り立てば, p*A+q*B = (ra*p+rb*q)*X + (sa*p+sb*q)*Y とすれば良いので成り立つ。

ということで, A, B に合わせられれば良いので,

• X だけで A, B とあわせることが出来る(i.e. A%X==0 かつ B%X==0)なら Y は何でも良いので -1
• そうでない場合は, Y の候補は 1 から 200 になるので, それを全部調べる

bool ok(int A, int B, int X, int Y) {
    bool flag = false;
    for (int r = 0; r*X <= A; r++) if ((A-r*X)%Y == 0) flag = true;
    if (!flag) return false;
    flag = false;
    for (int r = 0; r*X <= B; r++) if ((B-r*X)%Y == 0) flag = true;
    if (!flag) return false;
    return true;
}

class KingXNewCurrency {
public:
    int howMany(int A, int B, int X) {
        if (A%X == 0 && B%X == 0) return -1;
        int ans = 0;
        for (int i = 1; i <= 2000; i++) {
            if (ok(A, B, X, i)) ans++;
        }
        return ans;
    }
};