首页 > 代码库 > 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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。