首页 > 专题系列 > Java解POJ > POJ 3101 Astronomy [解题报告] Java
2013
11-12

POJ 3101 Astronomy [解题报告] Java

Astronomy

问题描述 :

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.

输入:

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 the answer as a common irreducible fraction, separate numerator and denominator by a space.

样例输入:

3
6 2 3

样例输出:

3 1

温馨提示:

解题代码:

import java.util.*;
import java.math.*;
public class Main {
	public static int[] p=new int[3000];
	public static int pc;
	public static int[] a=new int[3000];
	public static boolean[] che=new boolean[10001];
	public static void init(){
		int t1=2;
		while(t1*t1<=10000){
			int t2=t1*t1;
			while(t2<=10000){
				che[t2]=true;
				t2+=t1;
			}
			t1++;
			while(t1*t1<=10000&&che[t1])
				t1++;
		}
		for(int i=2;i< 10000;i++)
			if(!che[i])
				p[pc++]=i;
	}
	public static void solve(int k){
		for(int i=0;i< pc&&p[i]<=k;i++){
			int temp=0;
			while(k%p[i]==0){
				temp++;
				k/=p[i];
			}
			if(temp>a[i])
				a[i]=temp;
		}
	}
	public static int gcd(int x1,int x2){
		if(x2==0)
			return x1;
		return gcd(x2,x1%x2);
	}
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		init();
		int n=in.nextInt();
		int[] q=new int[1000];
		for(int i=0;i< n;i++){
			q[i]=in.nextInt();
			solve(q[i]);
		}
		BigInteger ans1=BigInteger.ONE;
		for(int i=0;i< pc;i++)
			for(int j=0;j< a[i];j++)
				ans1=ans1.multiply(BigInteger.valueOf(p[i]));
		int ans2=0;
		for(int i=1;i< n;i++)
			if(q[0]!=q[i])
				ans2=gcd(ans2,Math.abs(q[i]-q[0]));
		if(a[0]>0)
			ans1=ans1.divide(BigInteger.valueOf(2));
		else ans2*=2;
		if(ans2==0)
			ans1=BigInteger.ZERO;
		System.out.println(ans1+" "+ans2);
	}
}

  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  2. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  3. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!