首页 > 代码库 > POJ 3101 大数+gcd

POJ 3101 大数+gcd

2024-08-04 03:42:50   219人阅读

题目大意：

星星作圆周运动的周期给出，若已连成一条线，下一次所有星星在同一条线上的时间

 

用分数形式输出

这里我们可以利用追及问题来计算出两个星星之间连成一条直线的时间，也即速度快的星星追上速度慢的星星弧度PI

t = PI /abs (2PI / t1 - 2PI / t2) = t1 * t2 / (2 * abs(t1 - t2))

这样前面作为分子后面作为分母，每次得到一个分数记得利用gcd化简

 

然后把所有两两得到的时间差求个最小公倍数

分数的最大公倍数是分子求最小公倍数， 分母求最大公约数

 

 1 import java.util.*; 2 import java.math.*; 3  4 public class Main { 5  6     public static void main(String [] args){ 7         Scanner cin = new Scanner(System.in); 8         while(cin.hasNext()){ 9             Integer n;10             n = cin.nextInt();11             int [] t = new int[1005];12             for(int i = 0 ; i<n ; i++)13                 t[i] = cin.nextInt();14             15             long [] a = new long[1005];16             long [] b = new long[1005];17             for(int i = 0 ; i<n-1 ; i++){18                 int tmp1 = t[i] * t[i+1];19                 int tmp2 = 2 * Math.abs(t[i] - t[i+1]);20                 int k = GCD(tmp1 , tmp2);21                 a[i] = tmp1 / k;22                 b[i] = tmp2 / k;23             }24             25             BigInteger ans1 = BigInteger.valueOf(a[0]);26             BigInteger ans2 = BigInteger.valueOf(b[0]);27             for(int i = 1 ; i<n-1 ; i++){28                 BigInteger tmp = ans1.gcd(BigInteger.valueOf(a[i]));29                 ans1 = ans1.multiply(BigInteger.valueOf(a[i]));30                 ans1 = ans1.divide(tmp);31                 ans2 = ans2.gcd(BigInteger.valueOf(b[i]));32             }33             34             System.out.println(ans1 + " " + ans2);35         }36     }37     38     public static int GCD(int a , int b){39         if(b == 0) return a;40         return GCD(b , a%b);41     }42 }

 

POJ 3101 大数+gcd


联系
我们