Description
There are n planets in the planetary system of star X. They orbit star X in circular orbits located in the same plane. Their tangent velocities are constant. Directions of orbiting of all planets are the same.
Sometimes the event happens in this planetary system which is called planet parade. It is the moment when all planets and star X are located on the same straight line.
Your task is to find the length of the time interval between two consecutive planet parades.
Input
The first line of the input file contains n — the number of planets (2 ≤ n ≤ 1 000).
Second line contains n integer numbers ti — the orbiting periods of planets (1 ≤ ti ≤ 10 000). Not all of ti are the same.
Output
Output the answer as a common irreducible fraction, separate numerator and denominator by a space.
Sample Input
3 6 2 3Sample Output
3 1Hint
Source
Northeastern Europe 2005, Northern Subregion
题目大意：
给出n个星球绕中心天体飞行的周期，求最小运行多少可以让所有的星球在同一条直线上。
解题思路：
已知每个行星的角速度为vi = 2*π/Ti，选择一个行星T0作为坐标系，则其他行星的相对速度为vi' = (T0 - Ti)*2π/(T0*Ti)。则角度绕过半个圆周的时间为Ti' = π/vi' = (T0*Ti)/((T0 - Ti)*2) 这样就是求所有Ti‘的分子的LCM和所有Ti’分母的GCD。
注意相同周期的行星去重，大数处理
//0.5*L/abs(L/ti-L/tj)--->相差半周的时间 //(ti*tj) / (2*abs(ti-tj)) //令 (ti*tj)=bi; (2*abs(ti-tj))=ai; //相邻两个卫星平行的时间间隔di=bi/ai，问题转化为求这n-1个分数的最小公倍数 //分母p=gcd(a1,a2,...,an-1) //分子q=lcm(b1,b2,...,bn-1) //q/p 约分即得最终答案
分数的最小公倍数求法：设两分数为a/b,c/d（已化为最简形式），则最小公倍数为：lcm(a,c)/gcd(b,d)
#include<iostream> #include<cstdio> #include<cmath> using namespace std; const int N=1000; const int M=10000; int n; int t[N],r[N]; int c[M]; int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } int main() { int i,j,k; int a,b,g,d; while(scanf("%d",&n)!=EOF) { for(i=0; i<n; i++) scanf("%d",&t[i]); r[0]=1; for(i=1; i<N; i++) r[i]=0; d=0; for(i=1; i<n; i++) { if(t[i]!=t[0]) { b=t[i]*t[0]; //b[i]明显大于a[i] a=abs(t[i]-t[0])*2; g=gcd(a,b); a/=g;b/=g; //约分 d=gcd(a,d);//迭代求n个分母最大公约数 for(j=2; b>1; j++) //分解质因数 { if(b%j==0) { k=0; while(b%j==0)b/=j,k++; if(k>c[j])c[j]=k; } } } } //lrj结论: lcm(a,b)=p1^max(a1,b1)*p2^max(a2,b2)……pn^max(an,bn) b[i]明显大于a[i] //here: 预先计算出 所有bi的素因子个数 max 存放在 c[i] 数组中 //大整数乘法 r=∏(i^c[i]) {c[i]!=0} int tmp; for(i=0; i<M; i++) //大数乘法迭代求n个数最小公倍数 { for(j=0; j<c[i]; j++) { tmp=0; for(k=0; k<N; k++) { r[k]=r[k]*i+tmp;//tmp相当于是个进位~ tmp=r[k]/10000; r[k]%=10000; } } } i=999; while(i&&r[i]==0)i--; printf("%d",r[i]); i--; for(; i>=0; i--)printf("d",r[i]); printf(" %d\n",d); } return 0; }
java:
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(); } }
