poj 3101Astronomy(圆周追击+分数最小公倍数)

时间:2023-01-29 17:39:14
 /*
本题属于圆周追击问题:
假设已知两个圆周运动的物体的周期分别是a ,b, 设每隔时间t就会在同一条直线上
在同一条直线上的条件是 角度之差为 PI !
那么就有方程 (2PI/a - 2PI/b)* t=PI 所以就有 t=ab/(2|a-b|);
如果有多个物体, 就会有多个t值,所以每隔 所有 t值的最小公倍数的时间所有的物体就会在同一直线上! 另外:如果分数的分子分别是 a1, a2, ...., 和 b1, b2, ....
那么所有分数的最小公倍数就是lcm(a1, a2, ...)/gcd(b1, b2,....); 再有:如何求多个数的最小公倍数呢?
根据数论,每一个数都可以表示成素数的乘积的形式!
令p[i]存储素数,将a1,a2,...分别整除以p[i],直到除尽!并记录除以每个p[i]时的个数temp;
并更新该个数的最大值cnt[i]=max(temp, cnt[i]); 最后cnt[i]个p[i]分别相乘得到最终的结果就是所有数的最小公倍数!
*/
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#define M 10005
#define N 1005
using namespace std;
typedef long long LL;
LL p[M];
bool isP[M];
LL cnt[M];
LL q[N];
LL ans[N], endx;
LL top; void bigN(){//大数据的处理
LL c=;
endx=;
ans[]=;
for(LL i=; i<top; ++i)
for(LL j=; j<cnt[i]; ++j){
for(LL k=; k<=endx; ++k){
ans[k]=ans[k]*p[i] + c;
c=ans[k]/;
ans[k]%=;
}
if(c>){
ans[++endx]=c;
c=;
}
}
} void isPrime(){
LL i, j;
isP[]=;
for(i=; i<M; ++i){
if(!isP[i]) p[top++]=i;
for(j=; j<top && i*p[j]<M; ++j){
isP[i*p[j]]=;
if(i%p[j]==) break;
}
}
} void solve(LL k){
for(LL i=; i<top && p[i]<=k; ++i){
LL tmp=;
while(k%p[i]==){
++tmp;
k/=p[i];
} if(tmp>cnt[i])
cnt[i]=tmp;
}
} LL gcd(LL a, LL b){
while(b){
LL r=a%b;
a=b;
b=r;
}
return a;
} int main(){
LL n;
isPrime();
while(scanf("%lld", &n)!=EOF){
memset(cnt, , sizeof(cnt));
scanf("%lld", &q[]);
for(LL i=; i<n; ++i){
scanf("%lld", &q[i]);
LL tmp=q[]-q[i]> ? q[]-q[i] : q[i]-q[];
if(tmp!=){
LL GCD=gcd(tmp, q[]*q[i]);
solve(q[]*q[i]/GCD);
q[i]=tmp/GCD;
}
else q[i]=;
} LL ans2=;
for(LL i=; i<n; ++i)
ans2=gcd(ans2, q[i]);
if(cnt[]>)//除以2
--cnt[];
else ans2*=; bigN();
if(ans2==){
endx=;
ans[endx]=;
}
printf("%lld", ans[endx]);
for(int i=endx-; i>=; --i)
printf("%04lld", ans[i]);
printf(" %lld\n", ans2);
}
return ;
}
 //用java爽一下,处理大数
import java.util.Scanner;
import java.util.Arrays;
import java.math.*;
import java.io.BufferedInputStream;
class Main{
static int[] tt = new int[1005];
static int n;
static int top=0;
static boolean[] flag = new boolean[10005];
static int[] p = new int[10005];
static int[] q = new int[10005];
static int[] aa = new int[10005];
public static void isprime(){
int i, j;
Arrays.fill(flag, false);
for(i=2; i<=10000; ++i){
if(!flag[i]) p[top++]=i;
for(j=0; j<top && i*p[j]<=10000; ++j){
flag[i*p[j]]=true;
if(i%p[j]==0) break;
}
}
--top;
flag[1]=true;
}
public static void solve(int k){
int i, cnt;
for(i=0; i<=top && p[i]<=k; ++i){
cnt=0;
while(k%p[i]==0){
++cnt;
k=k/p[i];
}
if(cnt>aa[i])
aa[i]=cnt;
}
} public static int gcd(int a, int b){
while(b!=0){
int r=a%b;
a=b;
b=r;
}
return a;
} public static void main(String[] args){
isprime();
Scanner input = new Scanner(new BufferedInputStream(System.in));
n=input.nextInt();
q[0]=input.nextInt();
for(int i=1; i<n; ++i){
q[i]=input.nextInt();
int temp=Math.abs(q[0]-q[i]);
if(temp!=0){
int GCD=gcd(temp, q[0]*q[i]);
solve(q[0]*q[i]/GCD);
q[i]=temp/GCD;
}
else q[i]=0;
} BigInteger bigN = BigInteger.ONE;
for(int i=0; i<=top; ++i){
for(int j=0; j<aa[i]; ++j)
bigN=bigN.multiply(BigInteger.valueOf(p[i]));
}
for(int i=0; i<=top; ++i)
if(aa[i]!=0)
System.out.println(p[i]+" "+aa[i]);
int ans=0;
for(int i=1; i<n; ++i){
ans=gcd(ans, q[i]);
}
if(aa[0]>0)
bigN=bigN.divide(BigInteger.valueOf(2));
else ans*=2;
if(ans==0)
bigN=BigInteger.ZERO;
System.out.println(bigN+" "+ans);
}
}