Skip to content

Instantly share code, notes, and snippets.

@phonism
Created October 5, 2013 18:01
Show Gist options
  • Save phonism/6844184 to your computer and use it in GitHub Desktop.
Save phonism/6844184 to your computer and use it in GitHub Desktop.
LightOJ 1024 - Eid http://lightoj.com/volume_showproblem.php?problem=1024 求n个数的最大公约数,分解质因子,统计质因子。
import java.io.BufferedReader;
import java.io.IOError;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;
public class P1024 {
int[] prime = new int[10010];
boolean[] check = new boolean[10010];
int cnt = 0;
void getPrime() {
for (int i = 2; i < 10010; i++) {
if (check[i] == false)
prime[cnt++] = i;
for (int j = 0; j < cnt; j++) {
if (prime[j] * i >= 10010)
break;
check[i * prime[j]] = true;
}
}
}
public void run() {
Scanner cin = new Scanner(System.in);
PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
getPrime();
int[] tot = new int[10010];
int test = cin.nextInt();
for (int cas = 1; cas <= test; cas++) {
cout.print("Case " + cas + ": ");
int n = cin.nextInt();
Arrays.fill(tot, 0);
for (int num = 0; num < n; num++) {
int x = cin.nextInt();
int tmp = x;
for (int i = 0; i < cnt; i++) {
int count = 0;
while (tmp % prime[i] == 0) {
tmp /= prime[i];
count++;
}
if (tot[prime[i]] < count)
tot[prime[i]] = count;
}
}
BigInteger res = BigInteger.ONE;
for (int i = 2; i < 10010; i++) {
if (tot[i] > 0) {
res = res.multiply(BigInteger.valueOf(i).pow(tot[i]));
}
}
cout.println(res);
System.gc();
}
cout.flush();
}
public static void main(String args[]) {
new P1024().run();
}
class Scanner {
BufferedReader br;
StringTokenizer st;
Scanner(InputStream in) {
br = new BufferedReader(new InputStreamReader(in));
eat("");
}
void eat(String s) {
st = new StringTokenizer(s);
}
String nextLine() {
try {
return br.readLine();
} catch (IOException e) {
throw new IOError(e);
}
}
boolean hasNext() {
while (!st.hasMoreTokens()) {
String s = nextLine();
if (s == null)
return false;
eat(s);
}
return true;
}
String next() {
hasNext();
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment