首页 > 代码库 > POJ 3101 Astronomy
POJ 3101 Astronomy
这只是一个数学题~
题目大意:
给出n个星球绕中心天体飞行的周期,求最小运行多少可以让所有的星球在同一条直线上。
解题思路:
已知每个行星的角速度为vi = 2*π/Ti,选择一个行星T0作为坐标系,则其他行星的相对速度为vi‘ = (T0 - Ti)*2π/(T0*Ti)。则角度绕过半个圆周的时间为Ti‘ = π/vi‘ = (T0*Ti)/((T0 - Ti)*2)
这样就是求所有Ti‘的分子的LCM和所有Ti’分母的GCD。
注意相同周期的行星和数据范围
下面是代码:
import java.math.*; import java.util.*; public class Main{ public static void main(String[] args){ Scanner cin = new Scanner(System.in) ; int n=0,cnt; int [] t =new int [1005]; int [] ls =new int [1005]; BigInteger a,b,g,up = null,down=null; while(cin.hasNext()){ cnt=1; n=cin.nextInt(); for(int i=0;i<n;i++)t[i]=cin.nextInt(); Arrays.sort(t,0,n); ls[0]=t[0]; for(int i=1;i<n;i++){ if(t[i]!=t[i-1])ls[cnt++]=t[i]; } for(int i=1;i<cnt;i++){ a=BigInteger.valueOf(ls[i]*ls[0]); b=BigInteger.valueOf((ls[i]-ls[0])*2); g=a.gcd(b); if(i==1){ up=a.divide(g); down=b.divide(g); } else { a=a.divide(g); b=b.divide(g); up=up.multiply(a).divide(up.gcd(a)); down=down.gcd(b); } } System.out.println(up+" "+down); } cin.close(); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。