poj 3101Astronomy（圆周追击+分数最小公倍数）-白红宇

本题属于圆周追击问题：

假设已知两个圆周运动的物体的周期分别是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=0;

endx=0;

ans[0]=1;

for(LL i=0; i<top; ++i)

for(LL j=0; j<cnt[i]; ++j){

for(LL k=0; k<=endx; ++k){

ans[k]=ans[k]*p[i] + c;

c=ans[k]/10000;

ans[k]%=10000;

}

if(c>0){

ans[++endx]=c;

c=0;

}

void isPrime(){

LL i, j;

isP[1]=1;

for(i=2; i<M; ++i){

if(!isP[i]) p[top++]=i;

for(j=0; j<top && i*p[j]<M; ++j){

isP[i*p[j]]=1;

if(i%p[j]==0) break;

}

void solve(LL k){

for(LL i=0; i<top && p[i]<=k; ++i){

LL tmp=0;

while(k%p[i]==0){

++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, 0, sizeof(cnt));

scanf("%lld", &q[0]);

for(LL i=1; i<n; ++i){

scanf("%lld", &q[i]);

LL tmp=q[0]-q[i]>0 ? q[0]-q[i] : q[i]-q[0];

if(tmp!=0){

LL GCD=gcd(tmp, q[0]*q[i]);

solve(q[0]*q[i]/GCD);

q[i]=tmp/GCD;

}

else q[i]=0;

}

LL ans2=0;

for(LL i=1; i<n; ++i)

ans2=gcd(ans2, q[i]);

if(cnt[0]>0)//除以2

--cnt[0];

else ans2*=2;

bigN();

if(ans2==0){

endx=0;

ans[endx]=0;

}

printf("%lld", ans[endx]);

for(int i=endx-1; i>=0; --i)

printf("%04lld", ans[i]);

printf(" %lld\n", ans2);

}

return 0;

}

//用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);

}

本文转自小眼儿博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3891180.html，如需转载请自行联系原作者