POJ 3101 Astronomy (大数+LCM)
|
Astronomy
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 3 Sample Output 3 1
题目大意：一些行星绕恒星转，全部行星从全部共线，到下一次全部共线的时间。（题目给出的是每个行星的公转周期）
行星绕恒星环绕 共线会有两种情况：在恒星的同一侧，或在恒星的不同一侧（即不同方向上）
肯定和GCD和LCM有关的。我WA掉好多次。
下面红色部分就是解题思路，其他的可以不看-*-
①看到题目，直接求全部行星的周期的最小公倍数lcm，考虑共线的两种情况，则如果lcm%2==0，答案是（lcm/2,1），否则答案为（lcm，2）。 ? WA掉，漏了其他情况，想简单了。
②然后就求所有周期的lcm和gcd,同样考虑共线有2种情况，则gcd*=2,然后答案是约分后的（lcm，gcd）。 ? 再次WA掉。
③WA掉两次我就不自欺欺人了，这题没那么简单，还是老老实实推公式吧。 ?
对于两个行星，周期分别为a,b，设经过时间t两者可再次共线，则可得公式：t*(2*PI/a) - t*(2*PI/b) =m*PI,转换一下可得：
t=（a*b/(2*(a-b))）*m，易知m取1时t最小，所有t=a*b/(2*(a-b))，然后得出所有这样的t1,t2,..tk，求这些t的最小公倍数即答案（注意t要一直保持是分数，不要直接除成整数） ，就此编程提交，又WA。。。 ? ? 原因是存在两个行星的周期是一样的情况，即a-b=0.
④既然有相等周期，那么对于相等周期的只需要处理一个就行，那么就得去重了，好，去重，提交， ?WA。。。。?
⑤有溢出，先除后乘，期望不要溢出， ?提交， ? WA。。。。。
在算法正确，情况处理也全面的情况下，还WA，那就是数据的问题了，看看数据规模，求最小公倍数傻子都知道64位也溢出，必须大数搞，其实是我从没用过java的大数，所以对大数的题都是望而却步，不过这个题我都WA到现在了，怎么甘心放过它，用java搞一次，这是我第一次用java交代码。
大数+分数LCM+去重，这题就A了。
注意当只要两个不同周期的时候可以特判一下。
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
final static int maxn=1010;
public static int[] a = new int[maxn];
public static int[] b = new int[maxn];
public static int[] vis = new int[10*maxn];
public static long gcd(long a,long b){
return b==0?a:gcd(b,a%b);
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int i,n,k;
n=in.nextInt();k=0;
for(i=0;i<vis.length;i++) vis[i]=0;
for(i=0;i<n;i++){
int t=in.nextInt();
if(vis[t]==0){
a[k++]=t;
vis[t]=1;
}
}
long t1,g;
t1=a[0]*a[1];
t2=Math.abs(a[0]-a[1])*2;
if(k==2){
g=gcd(t1,t2);
System.out.println(t1/g+" "+t2/g);
}
else {
BigInteger d1,d2,d3,d4,x,y,v1,v2;
d1=BigInteger.valueOf(t1);
d2=BigInteger.valueOf(t2);
for(i=1;i<k-1;i++){
d3=BigInteger.valueOf(a[i]*a[i+1]);
d4=BigInteger.valueOf(Math.abs(a[i]-a[i+1])*2);
v1=d1.multiply(d4);
v2=d2.multiply(d3);
x=d1.multiply(d3);
y=v1.gcd(v2);
BigInteger temp=x.gcd(y);
d1=x.divide(temp);
d2=y.divide(temp);
}
System.out.println(d1+" "+d2);
}
}
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |