POJ 3101 Astronomy （数学）

POJ 3101 Astronomy （数学）

Description

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

36 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​​ ，然后求出最小公倍数即可。

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

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 + " "

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。