首页 > 代码库 > poj3101--Astronomy(分数的最小公倍数)
poj3101--Astronomy(分数的最小公倍数)
题目链接:点击打开链接
题目大意:有n个行星,给出每个行星的旋转的周期。问最少多少时间后n个行星会在一条直线上,初始点在一起,不存在全部的行星都有同一个周期
如果A行星的周期是t1。B行星的周期是t2(t2>t1),要在一条直线上,一定会执行的相差半个周期的倍数,时间(t/t2 - t/t1) % (1/2) = 0。也就是t*(t1-t2)/(t1*t2)%(1/2) = 0,要是时间最小。所以也就是差出一个半周期。也就是t = (t2-t1)/(t2*t1*2)这个t也就是A。B执行到一条直线上的最小时间,我们能够求出其它全部行星和A行星的在一条直线的最小时间,然后求出这个时间的最小公倍数。也就是整体的时间。
分数的最小公倍数 = (分子的最小公倍数)/(分母的最大公约数)
分数的最大公约数 = (分子的最大公约数)/ (分母的最小公倍数)
import java.util.*; import java.math.* ; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in) ; int n , i , cnt = 0 ; int a[] = new int[1010]; int b[] = new int[1010] ; BigInteger x , y , temp , u , v ; n = cin.nextInt() ; for(i = 0 ; i < n ; i++) a[i] = cin.nextInt() ; Arrays.sort(a,0,n) ; b[cnt++] = a[0] ; for(i = 1 ; i < n ; i++) if( a[i] != b[cnt-1] ) b[cnt++] = a[i] ; x = BigInteger.valueOf(b[1]*b[0]) ; y = BigInteger.valueOf((b[1]-b[0])*2) ; temp = x.gcd(y) ; x = x.divide(temp) ; y = y.divide(temp) ; for(i = 2 ; i < cnt ; i++) { u = BigInteger.valueOf(b[i]*b[0]) ; v = BigInteger.valueOf((b[i]-b[0])*2) ; temp = u.gcd(v) ; u = u.divide(temp) ; v = v.divide(temp) ; temp = x.gcd(u) ; x = x.multiply(u).divide(temp) ; y = y.gcd(v) ; } System.out.println(x + " " + y) ; } }
poj3101--Astronomy(分数的最小公倍数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。