行星连珠时间限制(普通/Java) : 8000 MS/ 16000 MS 运行内存限制 : 65536 KByte
总提交 : 57 测试通过 : 5 描述
通常用肉眼望去，当行星差不多处在一条直线上时，人们就称之为“行星连珠”。
n星连珠是指太阳系的n颗行星在同一时间位于同一条直线。
已知这n颗行星都是以太阳为圆心，做匀速圆周运动，且第i颗行星的公转周期为ti天（即绕圆周飞行一圈的时间）。
现在，Snow_storm想知道n星连珠每次出现的最少间隔时间是多少？ 输入
输入的第一行为正整数T(T<=300)，表示测试组数。 对于每组测试数据，有一个正整数n(2<=n<=10000)，表示有n颗行星 接下来的一行，共有n个正整数ti(1<=ti<=10000)，其中第i个数表示第i颗行星的公转周期。 输出
对于每组测试数据，输出最少的间隔时间。 样例输入 3 样例输出 Case 1: 210 题目来源 YB |
http://218.194.91.48/acmhome/problemdetail.do?&method=showdetail&id=1428
刚看到这题，很容易知道，就是求所有数的最小公倍数，但是乘积很大。
于是兴奋的写起JAVA大整数~~~
N久没写，有点手生。
敲完，提交，RE在第5组。
查了N久，怀疑数据中含0，除0了。。。 讨论版提问，果然~~
重判时，N范围从1000改到了10000。。。
（数据范围为1000时，我的JAVA代码应该是能AC的~~~ 囧~ 据出题人说：题目数据出水了，范围写错了~~ 各种囧）
秉着考方法（思路）不考运气的想法，出题人让我的代码华丽的TLE了~~~（写的方法不对~）
仔细想下，改用c++敲（比JAVA敲的顺手。。。）。。。
思路很简单，先枚举100以内的所有素数（10000开方后是100，所以10000以内的合数肯定有含有100以内的因素。不含有时，该数为质数）。。。
然后记录每个素数在所有数中出现了几次。。。
重复出现则除去（即除去共同因子）。。。
然后用大数乘法储存结果··· （当然这样还TLE了一次，囧，后来特判了一下，当新乘入的数为1时，则不进行大数乘法）。。。
算是擦边AC了吧？ 虽然数据确实很残暴。。。
后来把JAVA代码也改过了~~~~
=========================================================================================================
C++代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct BigInt{
int len,num[40000];
BigInt(){}
BigInt(int x){
len=1;
num[0]=x;
}
void mul(int x){
int i;
for(i=0;i<len;i++)
num[i]*=x;
for(i=0;i<len-1;i++)
if(num[i]>=100000){
num[i+1]+=num[i]/100000;
num[i]%=100000;
}
if(num[len-1]>=100000){
num[len]=num[len-1]/100000;
num[len-1]%=100000;
len++;
}
}
void print(){
printf("%d",num[--len]);
while(len--)
printf("%05d",num[len]);
puts("");
}
};
int prime[11000];
int rec[110],cnt;
int gcd(int x){
int i,j,k,num,res,m;
res=1;
for(i=0;i<cnt&& x>=rec[i];i++){
num=0;
while(x%rec[i]==0){
num++;
x/=rec[i];
}
if(num>0){
if(num<=prime[rec[i]]) continue;
else{
m=num-prime[rec[i]];
prime[rec[i]]=num;
while(m--)
res*=rec[i];
}
}
}
if(x && prime[x]==0){
res*=x;
prime[x]=1;
}
return res;
}
int init_(){
memset(prime,0,sizeof(prime));
int i,j;
cnt=0;
for(i=2;i<=100;i++){
if(prime[i]) continue;
for(j=i+i;j<=100;j+=i)
prime[j]=1;
rec[cnt++]=i;
}
}
int init_1(){
memset(prime,0,sizeof(prime));
}
int a[11000];
int cmp(int x,int y){
return x>y;
}
int main(){
int t,tt,n,i,tmp;
BigInt res;
scanf("%d",&t);
init_();
for(tt=1;tt<=t;tt++){
init_1();
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n,cmp);
res=BigInt(a[0]);
gcd(a[0]);
for(i=1;i<n;i++){
tmp=gcd(a[i]);
if(tmp==1) continue;
res.mul(tmp);
}
printf("Case %d: ",tt);
res.print();
}
return 0;
}
============================================================================================================
JAVA代码：
import java.util.*;
import java.math.*;
public class Main{
static int[] prime = new int[11000];
static int[] rec = new int[110];
static int cnt;
static int gcd(int x){
int i,j,k,num,res,m;
res=1;
for(i=0;i<cnt && x>=rec[i];i++){
num=0;
while((x%rec[i])==0){
num++;
x/=rec[i];
}
if(num>0){
if(num<=prime[rec[i]]) continue;
else{
m=num-prime[rec[i]];
prime[rec[i]]=num;
while(m>0){
m--;
res*=rec[i];
}
}
}
}
if(x>1 && prime[x]==0){
res*=x;
prime[x]=1;
}
return res;
}
static void init_(){
int i,j;
for(i=0;i<=100;i++)
prime[i]=0;
cnt=0;
for(i=2;i<=100;i++){
if(prime[i]==1) continue;
for(j=i+i;j<=100;j+=i)
prime[j]=1;
rec[cnt++]=i;
}
}
public static void main(String args[]){
Scanner cin = new Scanner(System.in);
int t,tt,n,j,i,tmp,m;
BigInteger res,now;
t = cin.nextInt();
init_();
for(tt=1;tt<=t;tt++){
for(j=0;j<=10000;j++) prime[j]=0;
n=cin.nextInt();
tmp=cin.nextInt();
res=BigInteger.valueOf(tmp);
gcd(tmp);
for(i=1;i<n;i++){
tmp=cin.nextInt();
m=gcd(tmp);
if(m==1) continue;
res=res.multiply(BigInteger.valueOf(m));
}
System.out.println("Case "+ tt + ": "+ res);
}
}
}