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