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