首页 > 代码库 > poj 3101 Astronomy

poj 3101 Astronomy

http://poj.org/problem?id=3101

这道题就是求所有分子的最小共倍数和分母的最大公约数。

 1 import java.math.BigInteger;
 2 import java.util.*;
 3 import java.util.Arrays;
 4 public class Main {
 5     public static void main(String []args)
 6     {
 7         Scanner cin=new Scanner(System.in);
 8         int n=cin.nextInt();
 9         int f2[]=new int[n];
10         BigInteger f[]=new BigInteger[2000];
11         BigInteger a[]=new BigInteger[2000];
12         BigInteger b[]=new BigInteger[2000];
13         BigInteger m1=new BigInteger("2");
14         for(int i=0; i<n; i++)
15         {
16             f2[i]=cin.nextInt();
17         }
18         Arrays.sort(f2);
19         int c=1;
20         f[0]=BigInteger.valueOf(f2[0]);
21         for(int i=1; i<n; i++)
22         {
23             if(f2[i]!=f2[i-1]) 
24             {
25                 f[c++]=BigInteger.valueOf(f2[i]);
26             }
27         }
28         int c1=0;
29         for(int i=1; i<c; i++)
30         {
31             a[c1]=(f[i].subtract(f[i-1])).multiply(m1);
32             b[c1]=f[i].multiply(f[i-1]);
33             BigInteger m=a[c1].gcd(b[c1]);
34             a[c1]=a[c1].divide(m);
35             b[c1]=b[c1].divide(m);
36             c1++;
37         }
38         BigInteger ans1=a[0];
39         BigInteger ans2=b[0];
40         BigInteger ans;
41         for(int i=1; i<c1; i++)
42         {
43             ans1=ans1.gcd(a[i]);
44             ans=ans2.multiply(b[i]);
45             ans2=ans.divide(ans2.gcd(b[i]));
46         }
47         ans=ans1.gcd(ans2);
48         System.out.println(ans2.divide(ans)+" "+ans1.divide(ans));
49         
50     }
51 }
View Code