TopCode SRM 346 Div1 Easy CommonMultiples
問題
数列a[i]が与えられる。
lower以上upper以下の整数のうち、a[i]項全ての倍数であるようなものはいくつあるか、求めよ。
制約条件
a[i]≦100
aの項数≦50
lower,upper≦2*10^9
方針
a[i]の最小公倍数を求めて、割り算で数を求めるだけ。
ソースコード
class CommonMultiples { public: int countCommMult(vector <int> a, int lower, int upper) { ll lcm=1; rep(i,a.size()){ ll g=__gcd(lcm,(ll)a[i]); lcm*=a[i]/g; if(lcm>upper)return 0; } return upper/lcm-(lower-1)/lcm; } };