首页 > 代码库 > poj 3101 Astronomy (java 分数的最小公倍数 gcd)

poj 3101 Astronomy (java 分数的最小公倍数 gcd)

2024-07-13 09:03:46   219人阅读

题目链接

要用大数，看了别人的博客，用java写的。

题意：求n个运动周期不完全相同的天体在一条直线上的周期。

分析：两个星球周期为a,b。则相差半周的长度为a*b/(2*abs(a-b)),对于n个只需求这n个

分数的最小公倍数即可。
分数的最小公倍数 = 分子的最小公倍数/分母的最大公约数
 
 1 import java.util.*; 2 import java.math.*; 3 public class Main { 4     public static int [] t = new int [1200]; 5     public static int [] tt = new int [1200]; 6     public static BigInteger [] fz = new BigInteger [1200]; 7     public static BigInteger [] fm = new BigInteger [1200]; 8      9     public static int gcd(int a, int b){10         return b==0?a:gcd(b, a%b);11     }12     public static void main(String args[]){13     int n, m;14      Scanner cin=new Scanner(System.in);15      n = cin.nextInt();16      for(int i = 0; i < n; i++)17          t[i] = cin.nextInt();18      Arrays.sort(t, 0, n);   //对数组排序19      m = 0;20      tt[m++] = t[0];21      for(int i = 1; i < n; i++)22          if(t[i]!=t[i-1])23              tt[m++] = t[i];24      for(int i = 1; i < m; i++){25          int a = tt[i]*t[0];26          int b = 2*(tt[i]-tt[0]);27          int g = gcd(a, b);28          fz[i] = BigInteger.valueOf(a/g);29          fm[i] = BigInteger.valueOf(b/g);30      }31      BigInteger t1, t2;32      t1 = fz[1]; t2 = fm[1];33      for(int i = 2; i < m; i++)34      {35          BigInteger aa = t1.multiply(fz[i]);36          BigInteger gg = t1.gcd(fz[i]);37          t1 = aa.divide(gg);38          t2 = t2.gcd(fm[i]);39      }40      System.out.println(t1+" "+t2);41     }42 }


联系
我们