Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <algorithm>
- using namespace std;
- #define forn( i, n ) for ( int i=0; i<(int)(n); i++ )
- const int MAXLEN = 400;
- const int BASE = 1000;
- struct tlong {
- int len;
- int dig[MAXLEN];
- tlong() { len = 1; dig[0] = 0; }
- void clear() {
- len = 1;
- dig[0] = 0;
- }
- tlong( int x ) {
- len = 0;
- while ( x > 0 ) dig[len++] = x%BASE, x/=BASE;
- }
- void reduce() {
- while ( len > 1 && dig[len-1] == 0 ) len--;
- }
- void move() {
- forn( i, len )
- {
- dig[i+1] += dig[i] / BASE;
- dig[i] %= BASE;
- }
- }
- void add( tlong& b )
- {
- if ( b.len > len )
- {
- for ( int i=len; i<=b.len; i++ ) dig[i] = 0;
- len = b.len;
- }
- dig[len+1] = dig[len] = 0;
- forn( i, b.len )
- {
- dig[i] += b.dig[i];
- if ( dig[i] >= BASE )
- {
- dig[i+1]++;
- dig[i] -= BASE;
- }
- }
- int j = b.len;
- while ( dig[j] >= BASE )
- {
- dig[j+1]++;
- dig[j] -= BASE;
- j++;
- }
- len = max( j+1, len );
- }
- void print()
- {
- reduce();
- printf( "%d", dig[len-1] );
- for ( int i=len-2; i>=0; i-- ) printf( "%03d", dig[i] );
- }
- void div( int x, bool& fl, tlong& res )
- {
- res.len = len;
- int c = 0;
- for ( int i=len-1; i>=0; i-- )
- {
- res.dig[i] = ( dig[i] + c ) / x;
- c = ( dig[i] + c ) % x * BASE;
- }
- res.reduce();
- fl = c == 0;
- }
- };
- tlong operator+( const tlong& a, const tlong& b )
- {
- tlong res;
- res.len = max( a.len, b.len ) + 2;
- forn( i, res.len ) res.dig[i] = ( i < a.len ? a.dig[i] : 0 ) + ( i < b.len ? b.dig[i] : 0 );
- res.move();
- res.reduce();
- return res;
- }
- tlong operator*( const tlong& a, const tlong& b )
- {
- tlong res;
- res.len = a.len + b.len + 7;
- forn( i, res.len ) res.dig[i] = 0;
- forn( i, a.len )
- forn( j, b.len )
- res.dig[i+j] += a.dig[i] * b.dig[j];
- res.move();
- res.reduce();
- return res;
- }
- tlong fact[470], res, z, fct;
- tlong a[2][2];
- int pp[230], kp;
- int main()
- {
- fact[0] = tlong( 1 );
- for ( int i=1; i<=465; i++ )
- fact[i] = fact[i-1] * tlong( i );
- for ( int i=2; i<=230; i++ )
- {
- bool ok = true;
- for ( int j=2; j*j<=i; j++ )
- if ( i%j == 0 )
- {
- ok = false;
- break;
- }
- if ( ok ) pp[kp++] = i;
- }
- int tc, n;
- scanf( "%d", &tc );
- while ( tc-- )
- {
- scanf( "%d", &n );
- res.clear();
- if ( n == 1 )
- {
- printf( "2\n" );
- continue;
- }
- for ( int i=0; i<=n-i; i++ )
- {
- z = fact[i] * fact[n-i];
- res.add( z );
- if ( i < n-i ) res.add( z );
- }
- a[0][1] = fact[n];
- a[0][0] = res;
- int fl = 0;
- bool fl1 = false, fl2 = false;
- forn( i, kp )
- {
- while ( true )
- {
- a[fl][0].div( pp[i], fl1, a[fl^1][0] );
- a[fl][1].div( pp[i], fl2, a[fl^1][1] );
- if ( fl1 && fl2 ) fl^=1;
- else break;
- }
- }
- a[fl][0].print();
- printf( "/" );
- a[fl][1].print();
- printf( "\n" );
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement