Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-10SRM346 (Practice)

SRM 346 CommonMultiples

|  SRM 346 CommonMultiples - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 346 CommonMultiples - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7408

  • やるだけ。
public class CommonMultiples {

	public long gcd(long a, long b) {
		return (b == 0) ? a : gcd(b, a%b);
	}
	
	public long lcm(long a, long b) {
		long gcd = gcd(a, b);
		return (a / gcd) * b;
	}
	
	
	public int countCommMult(int[] a, int lower, int upper) {
		long lo = lower;
		long up = upper;
		
		long l = 1;
		for (int i = 0 ; i < a.length ;i++) {
			l = lcm(l, a[i]);
			if (l > up || l <= 0) {
				return 0;
			}
		}	
		return (int)((up / l) - ((lo - 1) / l));
	}
}