(Relax 数论 1.17)POJ 3101 Astronomy(分数的最小公倍数)

import java.math.BigInteger;  
import java.util.Arrays;  
import java.util.Scanner;  
  
public class POJ_3101 {  
  
    public static void main(String[] args) {  
        Scanner scanner = new Scanner(System.in);  
  
        int n = scanner.nextInt();  
        int an[] = new int[n];  
        int a[] = new int[n];  
        int b[] = new int[n];  
  
        int i;  
        for (i = 0; i < n; ++i) {  
            an[i] = scanner.nextInt();  
        }  
  
        Arrays.sort(an);  
  
        int j;  
        for (i = 1, j = 1; i < n; ++i) {//去重  
            if (an[i] != a[i - 1]) {  
                an[j++] = an[i];  
            }  
        }  
  
        int k;  
        for (i = 1, k = 0; i < j; ++i) {//化简  
            a[k] = (an[i] - an[i - 1]) * 2;  
            b[k] = (an[i] * an[i - 1]);  
  
            int t = gcd(a[k], b[k]);  
  
            a[k] /= t;  
            b[k++] /= t;  
        }  
  
        BigInteger ans1 = BigInteger.valueOf(a[0]);//****    
        BigInteger ans2 = BigInteger.valueOf(b[0]);  
        BigInteger ans;  
        for (i = 1; i < k; ++i) {  
            ans1 = ans1.gcd(BigInteger.valueOf(a[i]));  
            ans = ans2.multiply(BigInteger.valueOf(b[i]));  
            ans2 = ans.divide(ans2.gcd(BigInteger.valueOf(b[i])));  
        }  
  
        ans = ans1.gcd(ans2);//化简输出...  
        System.out.println(ans2.divide(ans) + " " + ans1.divide(ans));  
  
    }  
  
    public static int gcd(int a, int b) {  
        int t;  
        if (a < b) {  
            t = a;  
            a = b;  
            b = t;  
        }  
        while (true) {  
            if (b == 0)  
                break;  
            t = a;  
            a = b;  
            b = t % b;  
        }  
        return a;  
    }  
}