Advertisement
BoxerTC

Untitled

Mar 30th, 2015
216
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.58 KB | None | 0 0
  1.  
  2. import java.io.File;
  3. import java.io.FileNotFoundException;
  4. import java.io.PrintWriter;
  5. import java.math.BigInteger;
  6. import java.util.Scanner;
  7.  
  8. public class Main  {
  9.     public static BigInteger ONE = BigInteger.ONE;
  10.     public static BigInteger ZERO = BigInteger.ZERO;
  11.     public static BigInteger TWO = BigInteger.valueOf(2);
  12.     static class frac{
  13.         BigInteger num , den;
  14.         frac(){ num = den = ZERO;}
  15.         public frac( BigInteger a , BigInteger b ){
  16.                 if( b.equals( ZERO ) ) {
  17.                     num = ONE;
  18.                     den = ZERO;
  19.                 } else if( a.equals( ZERO ) ){
  20.                     num = ZERO;
  21.                     den = ONE;
  22.                 }else{
  23.                         if( b.compareTo(ZERO) == -1 ){
  24.                             a = a.negate();
  25.                             b = b.negate();
  26.                         }
  27.                         BigInteger g = (a.abs()).gcd(b.abs());
  28.                         num = a.divide(g) ;
  29.                         den = b.divide(g);
  30.                 }
  31.         }
  32.     };
  33.     public static boolean Less( frac a , frac b ){
  34.             return ( a.num.multiply( b.den ) ).compareTo( b.num.multiply( a.den ) ) == -1;
  35.     }
  36.     public static boolean Higher( frac a , frac b ){
  37.             return ( a.num.multiply( b.den ) ).compareTo( b.num.multiply( a.den ) ) == 1;
  38.     }
  39.     boolean equals ( frac A , frac B ){ return A.num.equals(B.num) && A.den.equals(B.den);}
  40.     public static frac sum( frac A , frac B ){ return new frac( A.num .multiply( B.den ).add( B.num .multiply( A.den ) ) , A.den.multiply( B.den ) ) ;}
  41.     public static frac resta( frac A , frac B ){ return new frac( A.num .multiply( B.den ).subtract( B.num .multiply( A.den ) ) , A.den.multiply( B.den ) ) ;}
  42.  
  43.     public static frac mult( frac A , frac B ){ return new frac( A.num.multiply( B.num ) , A.den.multiply( B.den ) ) ;}
  44.     public static frac div( frac A , frac B ){ return new frac( A.num.multiply( B.den ) , A.den.multiply( B.num ) ) ;}
  45.     public static frac abs( frac A ){ return new frac( A.num.abs() , A.den.abs() );}
  46.  
  47.     public static void invert( frac A[][] , frac B[][] , int n ){
  48.     for( int i = 0 ; i < n ; ++i ){
  49.         int jmax = i ;
  50.         for( int j = i + 1 ; j < n ; ++j )
  51.             if( Higher( abs( A[ j ][ i ] ) , abs( A[ jmax ][ i ] ) ) ) jmax = j;
  52.         for( int j = 0 ; j < n ; ++j ){
  53.                     frac temp;
  54.                     temp = A[ i ][ j ];
  55.                     A[ i ][ j ] = A[ jmax ][ j ];
  56.                     A[ jmax ][ j ] = temp;
  57.                    
  58.                     temp = B[ i ][ j ];
  59.                     B[ i ][ j ] = B[ jmax ][ j ];
  60.                     B[ jmax ][ j ] = temp;
  61.                 }
  62.  
  63.         frac tmp = A[ i ][ i ];
  64.         for( int j = 0 ; j < n ; ++j ){
  65.                     A[ i ][ j ] = div( A[ i ][ j ] , tmp );
  66.                     B[ i ][ j ] = div( B[ i ][ j ] , tmp );
  67.                 }
  68.         for( int j = 0 ; j < n ; ++j ){
  69.             if( i == j )continue;
  70.             tmp = A[ j ][ i ];
  71.             for( int k = 0 ; k < n ; ++k ){
  72.                             A[ j ][ k ] = resta( A[ j ][ k ] , mult( A[ i ][ k ] , tmp ) );
  73.                             B[ j ][ k ] = resta( B[ j ][ k ] , mult( B[ i ][ k ] , tmp ) );
  74.                         }
  75.         }
  76.     }
  77.     }
  78.     public static String input = "divide.in";
  79.     public static String output = "divide.out";
  80.    
  81.     public static void main(String[] args) throws FileNotFoundException {
  82.         Scanner cin = new Scanner( new File(input) );
  83.         int n = cin.nextInt();
  84.         cin.close();
  85.        
  86.         PrintWriter wt = new PrintWriter(output);
  87.         frac A[][] = new frac[ n + 1 ][ n + 1 ];
  88.         for( int i = 0 ; i <= n ; ++i )
  89.             for( int j = 0 ; j <= n ; ++j ) A[ i ][ j ] = new frac( ONE , ONE );
  90.         frac B[][] = new frac[ n + 1 ][ n + 1 ];
  91.         for( int i = 0 ; i <= n ; ++i )
  92.             for( int j = 0 ; j <= n ; ++j ) B[ i ][ j ] = new frac( ONE , ONE );
  93.         for( int i = 0 ; i <= n ; ++i ) A[ i ][ n ] = new frac( ONE , ONE );
  94.         for( int i = 0 ; i <= n ; ++i )
  95.             for( int j = n - 1 ; j >= 0 ; --j )
  96.                 A[ i ][ j ] = mult( new frac( BigInteger.valueOf(i) , ONE ) , A[ i ][ j + 1 ] );
  97.         B[ 0 ][ 0 ] = new frac( ONE , ONE );
  98.         for( int i = 1 ; i <= n ; ++i ) B[ i ][ 0 ] = mult( new frac( TWO , ONE ) , B[ i - 1 ][ 0 ] );
  99.         invert( A , B , n + 1 );
  100.         wt.println( n );
  101.         for( int i = 0 ; i <= n ; ++i ){
  102.             wt.print( B[ i ][ 0 ].num + "/" + B[ i ][ 0 ].den );
  103.             if( i == n ) wt.println("");
  104.             else wt.print(" ");
  105.         }
  106.         wt.close();
  107.     }
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement