poj3101——Astronomy(大数数学&gcd)

Description

Input

Output

Sample Input

3
6 2 3  

Sample Output

3 1  

Hint

Source

Northeastern Europe 2005, Northern Subregion

题目大意：

给出n个星球绕中心天体飞行的周期，求最小运行多少可以让所有的星球在同一条直线上。

解题思路：

已知每个行星的角速度为vi = 2*π/Ti，选择一个行星T0作为坐标系，则其他行星的相对速度为vi' = (T0 - Ti)*2π/(T0*Ti)。则角度绕过半个圆周的时间为Ti' = π/vi' = (T0*Ti)/((T0 - Ti)*2)


这样就是求所有Ti‘的分子的LCM和所有Ti’分母的GCD。

注意相同周期的行星去重，大数处理

1.   
2. //0.5*L/abs(L/ti-L/tj)--->相差半周的时间  
3.   
4. //(ti*tj) / (2*abs(ti-tj))  
5. //令 (ti*tj)=bi; (2*abs(ti-tj))=ai;  
6.   
7. //相邻两个卫星平行的时间间隔di=bi/ai，问题转化为求这n-1个分数的最小公倍数  
8.   
9.   
10. //分母p=gcd(a1,a2,...,an-1)  
11. //分子q=lcm(b1,b2,...,bn-1)  
12.   
13. //q/p 约分即得最终答案  

分数的最小公倍数求法：设两分数为a/b,c/d（已化为最简形式），则最小公倍数为：lcm(a,c)/gcd(b,d)

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

const int N=1000;
const int M=10000;
int n;
int t[N],r[N];
int c[M];
int gcd(int a,int b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
int main()
{
    int i,j,k;
    int a,b,g,d;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0; i<n; i++)
            scanf("%d",&t[i]);
        r[0]=1;
        for(i=1; i<N; i++) r[i]=0;
        d=0;
        for(i=1; i<n; i++)
        {
            if(t[i]!=t[0])
            {
                b=t[i]*t[0]; //b[i]明显大于a[i]
                a=abs(t[i]-t[0])*2;
                g=gcd(a,b);


                a/=g;b/=g; //约分
                d=gcd(a,d);//迭代求n个分母最大公约数
                for(j=2; b>1; j++) //分解质因数
                {
                    if(b%j==0)
                    {
                        k=0;
                        while(b%j==0)b/=j,k++;
                        if(k>c[j])c[j]=k;
                    }
                }
            }
        }
        //lrj结论:  lcm(a,b)=p1^max(a1,b1)*p2^max(a2,b2)……pn^max(an,bn) b[i]明显大于a[i]
        //here:     预先计算出 所有bi的素因子个数 max 存放在 c[i] 数组中
        //大整数乘法 r=∏(i^c[i]) {c[i]!=0}
        int tmp;
        for(i=0; i<M; i++) //大数乘法迭代求n个数最小公倍数
        {
            for(j=0; j<c[i]; j++)
            {
                tmp=0;
                for(k=0; k<N; k++)
                {
                    r[k]=r[k]*i+tmp;//tmp相当于是个进位~
                    tmp=r[k]/10000;
                    r[k]%=10000;
                }
            }
        }
        i=999;
        while(i&&r[i]==0)i--;
        printf("%d",r[i]);
        i--;
        for(; i>=0; i--)printf("%04d",r[i]);
        printf(" %d\n",d);
    }
    return 0;
}

java:

import java.math.*;
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in) ;
        int n=0,cnt;
        int [] t =new int [1005];
        int [] ls =new int [1005];
        BigInteger a,b,g,up = null,down=null;
        while(cin.hasNext()){
        cnt=1;
        n=cin.nextInt();
        for(int i=0;i<n;i++)t[i]=cin.nextInt();
        Arrays.sort(t,0,n);
        ls[0]=t[0];
        for(int i=1;i<n;i++){
        if(t[i]!=t[i-1])ls[cnt++]=t[i];
        }
        for(int i=1;i<cnt;i++){
        a=BigInteger.valueOf(ls[i]*ls[0]);
        b=BigInteger.valueOf((ls[i]-ls[0])*2);
        g=a.gcd(b);
        if(i==1){
        up=a.divide(g);
        down=b.divide(g);
        }
        else {
a=a.divide(g);
b=b.divide(g);
up=up.multiply(a).divide(up.gcd(a));
down=down.gcd(b);
}
        }
        System.out.println(up+" "+down);
        }
        cin.close();
    }
}