POJ 3101 Astronomy （數學）

Description

There are n planets in the planetary system of star X. They orbit star X in circular orbits located in the same plane. Their tangent velocities are constant. Directions of orbiting of all planets are the same.

Sometimes the event happens in this planetary system which is called planet parade. It is the moment when all planets and star X are located on the same straight line.

Your task is to find the length of the time interval between two consecutive planet parades.

Input

The first line of the input file contains n — the number of planets (2 ≤ n ≤ 1 000).

Second line contains n integer numbers ti — the orbiting periods of planets (1 ≤ ti ≤ 10 000). Not all of ti are the same.

Output

Output the answer as a common irreducible fraction, separate numerator and denominator by a space.

Sample Input

3
6 2 3      

Sample Output

3 1      

題意

給出 ​

​n​

​ 個行星圍繞恒星轉動的周期，剛開始所有的行星都在恒星的一側并且排成一條直線。問最少再經過多長時間所有的行星出現在同一條直線上。

思路

我們先來看兩個行星的情況，假設 ​

​t​

​ 時間之後這兩個行星會出現在同一條直線上。

則 2πT0t−2πT1t=πk 其中 k

化簡得： 2(T1−T0)tT0T1=k ，為使 ​

​k​

​ 為最小正整數， t=T0T12(T1−T0)t

對于兩個行星以上的情況，可以兩兩計算得到的 ​

​t​

​ ，然後求出最小公倍數即可。

分式的最小公倍數求法： （分子分母約分到最簡形式）

AC 代碼

import java.util.Scanner;
import java.math.BigInteger;

public class Main
    private static Scanner cin;

    public static void main(String[] args) {
        int N;
        BigInteger on, lcm = null, gc = null;
        cin = new Scanner(System.in);
        N = cin.nextInt();
        on = cin.nextBigInteger();
        lcm = on;
        for (int i = 1; i < N; i++) {
            BigInteger x;
            x = cin.nextBigInteger();
            if (i == 1) {
                lcm = lcm.multiply(x);
                gc = (x.subtract(on)).abs().multiply(new BigInteger("2"));
                BigInteger r = lcm.gcd(gc);
                lcm = lcm.divide(r);
                gc = gc.divide(r);
            } else {
                BigInteger n1 = on.multiply(x);
                BigInteger n2 = (x.subtract(on)).abs().multiply(new BigInteger("2"));
                BigInteger r = n1.gcd(n2);
                n1 = n1.divide(r);
                n2 = n2.divide(r);
                lcm = lcm.divide(lcm.gcd(n1)).multiply(n1);
                gc = gc.gcd(n2);
                r = lcm.gcd(gc);
                lcm = lcm.divide(r);
                gc = gc.divide(r);
            }
        }
        System.out.println(lcm + " "