1 /*  2    本题属于圆周追击问题：  3      假设已知两个圆周运动的物体的周期分别是a ,b, 设每隔时间t就会在同一条直线上   4      在同一条直线上的条件是 角度之差为 PI !  5      那么就有方程 （2PI/a - 2PI/b）* t=PI  所以就有 t=ab/(2|a-b|);  6      如果有多个物体， 就会有多个t值，所以每隔 所有 t值的最小公倍数的时间所有的物体就会在同一直线上！  7        8      另外：如果分数的分子分别是 a1, a2, ...., 和 b1, b2, ....  9      那么所有分数的最小公倍数就是lcm(a1, a2, ...)/gcd(b1, b2,....); 10       11      再有：如何求多个数的最小公倍数呢？ 12      根据数论，每一个数都可以表示成素数的乘积的形式！  13      令p[i]存储素数，将a1,a2,...分别整除以p[i]，直到除尽！并记录除以每个p[i]时的个数temp; 14      并更新该个数的最大值cnt[i]=max(temp, cnt[i]);  15       16      最后cnt[i]个p[i]分别相乘得到最终的结果就是所有数的最小公倍数！  17 */ 18 #include<iostream> 19 #include<cstring> 20 #include<cmath> 21 #include<cstdio> 22 #define M 10005 23 #define N 1005 24 using namespace std; 25 typedef long long LL; 26 LL p[M]; 27 bool isP[M]; 28 LL cnt[M]; 29 LL q[N]; 30 LL ans[N], endx; 31 LL top; 32  33 void bigN(){//大数据的处理 34    LL c=0; 35    endx=0; 36    ans[0]=1; 37    for(LL i=0; i<top; ++i) 38       for(LL j=0; j<cnt[i]; ++j){ 39           for(LL k=0; k<=endx; ++k){ 40              ans[k]=ans[k]*p[i] + c; 41              c=ans[k]/10000; 42              ans[k]%=10000; 43           } 44           if(c>0){ 45              ans[++endx]=c; 46              c=0; 47           } 48       } 49 } 50  51 void isPrime(){ 52    LL i, j; 53    isP[1]=1; 54    for(i=2; i<M; ++i){ 55        if(!isP[i])  p[top++]=i; 56        for(j=0; j<top && i*p[j]<M; ++j){ 57            isP[i*p[j]]=1; 58            if(i%p[j]==0) break; 59        } 60    } 61 } 62  63 void solve(LL k){ 64    for(LL i=0; i<top && p[i]<=k; ++i){ 65        LL tmp=0; 66        while(k%p[i]==0){ 67           ++tmp; 68           k/=p[i]; 69        } 70         71        if(tmp>cnt[i]) 72           cnt[i]=tmp; 73    } 74 } 75  76 LL gcd(LL a, LL b){ 77    while(b){ 78       LL r=a%b; 79       a=b; 80       b=r; 81    } 82    return a; 83 } 84  85 int main(){ 86    LL n; 87    isPrime(); 88    while(scanf("%lld", &n)!=EOF){ 89           memset(cnt, 0, sizeof(cnt)); 90           scanf("%lld", &q[0]);  91        for(LL i=1; i<n; ++i){ 92            scanf("%lld", &q[i]); 93            LL tmp=q[0]-q[i]>0 ? q[0]-q[i] : q[i]-q[0]; 94            if(tmp!=0){ 95               LL GCD=gcd(tmp, q[0]*q[i]); 96               solve(q[0]*q[i]/GCD); 97               q[i]=tmp/GCD; 98            } 99            else q[i]=0;100        } 101        102        LL ans2=0;103        for(LL i=1; i<n; ++i)104           ans2=gcd(ans2, q[i]);105        if(cnt[0]>0)//除以2 106            --cnt[0];107        else ans2*=2; 108      109        bigN();110        if(ans2==0){111            endx=0;112            ans[endx]=0;113        }114        printf("%lld", ans[endx]);115        for(int i=endx-1; i>=0; --i)116           printf("%04lld", ans[i]);117        printf(" %lld\n", ans2);118    }119    return 0;120 } 

 1 //用java爽一下，处理大数 2 import java.util.Scanner; 3 import java.util.Arrays; 4 import java.math.*; 5 import java.io.BufferedInputStream; 6 class Main{ 7    static int[] tt = new int[1005]; 8    static int n; 9    static int top=0;10    static boolean[] flag = new boolean[10005];11    static int[] p = new int[10005];12    static int[] q = new int[10005];13    static int[] aa = new int[10005];14    public static void isprime(){15        int i, j;16        Arrays.fill(flag, false);17        for(i=2; i<=10000; ++i){18            if(!flag[i]) p[top++]=i;19            for(j=0; j<top && i*p[j]<=10000; ++j){20               flag[i*p[j]]=true;21               if(i%p[j]==0) break;22            }     23        }24        --top;25        flag[1]=true;26    }27    public static void solve(int k){28         int i, cnt;29         for(i=0; i<=top && p[i]<=k; ++i){30            cnt=0;31            while(k%p[i]==0){32                 ++cnt;33                 k=k/p[i];34              }35            if(cnt>aa[i])36               aa[i]=cnt;37         }38    }39 40    public static int gcd(int a, int b){41        while(b!=0){42           int r=a%b;43           a=b;44           b=r;45        }46        return a;47    }48    49    50    public static  void main(String[] args){51        isprime();52        Scanner input = new Scanner(new BufferedInputStream(System.in));53        n=input.nextInt();54        q[0]=input.nextInt();55        for(int i=1; i<n; ++i){56            q[i]=input.nextInt();57            int temp=Math.abs(q[0]-q[i]);58            if(temp!=0){59               int GCD=gcd(temp, q[0]*q[i]);60               solve(q[0]*q[i]/GCD);61               q[i]=temp/GCD;62            }63            else q[i]=0;64        }65        66        BigInteger bigN = BigInteger.ONE;67        for(int i=0; i<=top; ++i){68            for(int j=0; j<aa[i]; ++j)69               bigN=bigN.multiply(BigInteger.valueOf(p[i]));70        }71        for(int i=0; i<=top; ++i)72           if(aa[i]!=0)73             System.out.println(p[i]+" "+aa[i]);74        int ans=0;75        for(int i=1; i<n; ++i){76            ans=gcd(ans, q[i]);77        }78        if(aa[0]>0)79             bigN=bigN.divide(BigInteger.valueOf(2));80        else ans*=2;81        if(ans==0)82             bigN=BigInteger.ZERO;83        System.out.println(bigN+" "+ans);84    }85 }