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]);

              q[i]=temp/GCD;

       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;

           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，如需轉載請自行聯系原作者