当前位置：网站首页>POJ 3101 Astronomy （数学）

POJ 3101 Astronomy （数学）

2022-08-10 10:33:00 【51CTO】

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

Sample Output

题意

给出 n 个行星围绕恒星转动的周期，刚开始所有的行星都在恒星的一侧并且排成一条直线。问最少再经过多长时间所有的行星出现在同一条直线上。

思路

我们先来看两个行星的情况，假设 t 时间之后这两个行星会出现在同一条直线上。

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

化简得： 2(T1−T0)tT0T1=k ，为使 k 为最小正整数， t=T0T12(T1−T0)t

对于两个行星以上的情况，可以两两计算得到的 t ，然后求出最小公倍数即可。

分式的最小公倍数求法： （分子分母约分到最简形式）

ab cd:lcm(a,c)gcd(b,d)

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 
       
       + 
       
       " "
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.