2138.cpp

来自「哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码」· C++ 代码 · 共 48 行

/*  This Code is Submitted by wywcgs for Problem 2138 on 2005-11-11 at 16:46:03 */ 
#include <cstdio>

const int MAX = 8;
const int LIMIT = 1000000000;

long long gcd(long long, long long);

int main()
{
	int T, w, t;
	int i;
	long long p[MAX], P, a;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &w);
		for(i = 0; i < w; i++) {
			scanf("%lld", &p[i]);
		}
		P = 1;
		for(i = 0; i < w; i++) {
			if(P < p[i]) {
				a = gcd(p[i], P);
			} else {
				a = gcd(P, p[i]);
			}
			P *= p[i] / a;
		}
		if(P >= LIMIT) {
			printf("More than a billion.\n");
		} else {
			printf("%lld\n", P);
		}
	}
	
	return 0;
}

long long gcd(long long a, long long b)
{
	if(a % b == 0) {
		return b;
	} else {
		return gcd(b, a % b);
	}
}