Advertisement
Guest User

Untitled

a guest
Jul 21st, 2017
183
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. #define forn( i, n ) for ( int i=0; i<(int)(n); i++ )
  6. const int MAXLEN = 400;
  7. const int BASE = 1000;
  8.  
  9. struct tlong {
  10.   int len;
  11.   int dig[MAXLEN];
  12.  
  13.   tlong() { len = 1; dig[0] = 0; }
  14.  
  15.   void clear() {
  16.     len = 1;
  17.     dig[0] = 0;
  18.   }
  19.  
  20.   tlong( int x ) {
  21.     len = 0;
  22.     while ( x > 0 ) dig[len++] = x%BASE, x/=BASE;
  23.   }
  24.  
  25.   void reduce() {
  26.     while ( len > 1 && dig[len-1] == 0 ) len--;
  27.   }
  28.  
  29.   void move() {
  30.     forn( i, len )
  31.     {
  32.       dig[i+1] += dig[i] / BASE;
  33.       dig[i] %= BASE;
  34.     }
  35.   }
  36.  
  37.   void add( tlong& b )
  38.   {
  39.     if ( b.len > len )
  40.     {
  41.       for ( int i=len; i<=b.len; i++ ) dig[i] = 0;
  42.       len = b.len;
  43.     }
  44.     dig[len+1] = dig[len] = 0;
  45.     forn( i, b.len )
  46.     {
  47.       dig[i] += b.dig[i];
  48.       if ( dig[i] >= BASE )
  49.       {
  50.         dig[i+1]++;
  51.         dig[i] -= BASE;
  52.       }
  53.     }
  54.     int j = b.len;
  55.     while ( dig[j] >= BASE )
  56.     {
  57.       dig[j+1]++;
  58.       dig[j] -= BASE;
  59.       j++;
  60.     }
  61.     len = max( j+1, len );
  62.   }
  63.  
  64.   void print()
  65.   {
  66.     reduce();
  67.     printf( "%d", dig[len-1] );
  68.     for ( int i=len-2; i>=0; i-- ) printf( "%03d", dig[i] );
  69.   }
  70.  
  71.   void div( int x, bool& fl, tlong& res )
  72.   {
  73.     res.len = len;
  74.     int c = 0;
  75.     for ( int i=len-1; i>=0; i-- )
  76.     {
  77.       res.dig[i] = ( dig[i] + c ) / x;
  78.       c = ( dig[i] + c ) % x * BASE;
  79.     }
  80.     res.reduce();
  81.     fl = c == 0;
  82.   }
  83. };
  84.  
  85. tlong operator+( const tlong& a, const tlong& b )
  86. {
  87.   tlong res;
  88.   res.len = max( a.len, b.len ) + 2;
  89.   forn( i, res.len ) res.dig[i] = ( i < a.len ? a.dig[i] : 0 ) + ( i < b.len ? b.dig[i] : 0 );
  90.   res.move();
  91.   res.reduce();
  92.   return res;
  93. }
  94.  
  95. tlong operator*( const tlong& a, const tlong& b )
  96. {
  97.   tlong res;
  98.   res.len = a.len + b.len + 7;
  99.   forn( i, res.len ) res.dig[i] = 0;
  100.   forn( i, a.len )
  101.     forn( j, b.len )
  102.       res.dig[i+j] += a.dig[i] * b.dig[j];
  103.   res.move();
  104.   res.reduce();
  105.   return res;
  106. }
  107.  
  108. tlong fact[470], res, z, fct;
  109. tlong a[2][2];
  110. int pp[230], kp;
  111.  
  112. int main()
  113. {
  114.   fact[0] = tlong( 1 );
  115.   for ( int i=1; i<=465; i++ )
  116.     fact[i] = fact[i-1] * tlong( i );  
  117.  
  118.   for ( int i=2; i<=230; i++ )
  119.   {
  120.     bool ok = true;
  121.     for ( int j=2; j*j<=i; j++ )
  122.       if ( i%j == 0 )
  123.       {
  124.         ok = false;
  125.         break;
  126.       }
  127.     if ( ok ) pp[kp++] = i;
  128.   }
  129.  
  130.   int tc, n;
  131.   scanf( "%d", &tc );
  132.   while ( tc-- )
  133.   {
  134.     scanf( "%d", &n );
  135.     res.clear();
  136.  
  137.     if ( n == 1 )
  138.     {
  139.       printf( "2\n" );
  140.       continue;
  141.     }
  142.  
  143.     for ( int i=0; i<=n-i; i++ )
  144.     {
  145.       z = fact[i] * fact[n-i];
  146.       res.add( z );
  147.       if ( i < n-i ) res.add( z );
  148.     }
  149.  
  150.     a[0][1] = fact[n];
  151.     a[0][0] = res;
  152.  
  153.     int fl = 0;
  154.     bool fl1 = false, fl2 = false;
  155.     forn( i, kp )
  156.     {
  157.       while ( true )
  158.       {
  159.         a[fl][0].div( pp[i], fl1, a[fl^1][0] );
  160.         a[fl][1].div( pp[i], fl2, a[fl^1][1] );
  161.         if ( fl1 && fl2 ) fl^=1;
  162.         else break;
  163.       }
  164.     }
  165.  
  166.     a[fl][0].print();
  167.     printf( "/" );
  168.     a[fl][1].print();
  169.     printf( "\n" );
  170.   }
  171. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement