3101.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3101  User Id:fzk 
Memory:7124K  Time:6350MS
Language:Java  Result:Accepted

Source 

import java.util.*;
import java.math.*;

public class Main {
	static BigInteger[] a , b;
	static HashSet s = new HashSet( );
	static BigInteger clac( int l, int r ) {
		if( r <= l+1 )
			return a[l];
		int c = (l+r)/2;
		a[l] = clac( l, c );
		a[r-1] = clac( c, r );
		return a[l].divide( a[l].gcd( a[r-1] ) ).multiply( a[r-1] );
	}
	
	static public void main( String [] str ) throws Exception{
		Scanner cin = new Scanner(System.in);
		int n = cin.nextInt();
		
		BigInteger as = BigInteger.ZERO, bs = BigInteger.ZERO, 
			temp;
		
		a = new BigInteger[n];
		b = new BigInteger[n];
		
		for( int i=0; i<n; i++ ) {
			int t = cin.nextInt();
			if( s.contains( Integer.valueOf( t ) ) ) {
				i--;
				n--;
				continue;
			}
			s.add( Integer.valueOf( t ) );
			a[i] = BigInteger.valueOf( 2 );
			b[i] = BigInteger.valueOf( t );
		}
		
		BigInteger sum = BigInteger.ONE;
		
		for( int i=1; i<n; i++ ) {
			as = a[0].multiply(b[i]).subtract(
					a[i].multiply(b[0]) );
			if( as.compareTo( BigInteger.ZERO ) <= 0 )
				as = as.negate();
			bs = b[0].multiply( b[i] );
			
			temp = bs.gcd( as );
			a[i] = bs.divide( temp );
			b[i] = as.divide( temp );
			sum = sum.multiply( b[i] );
			
	        }
		
		for( int i=1; i<n; i++ )
			a[i] = a[i].multiply( sum ).divide( b[i] );
			
		a[0] = BigInteger.ONE;
		a[1] = clac( 1, n );
	
		a[0] = sum.gcd( a[1] );
		a[1] = a[1].divide( a[0] );
		sum = sum.divide( a[0] );
		System.out.println( a[1] + " " + sum );
		return;
	}
}