BZOJ-1498: [NOI2006]神奇的口袋

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1498

我们神奇的发现把x[1],x[2]...x[n]映射到1,2,...n是等价的，所以直接算就好了嗯。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

const int maxn = 20000 ;

 

bool flag[ maxn + 10 ] ;

int p[ maxn ] , pn = 0 ;

 

inline void Init(  ) {

        memset( flag , true , sizeof( flag ) ) ;

        for ( int i = 2 ; i <= maxn ; ++ i ) if ( flag[ i ] ) {

                p[ ++ pn ] = i ;

                for ( int j = i << 1 ; j <= maxn ; j += i ) flag[ j ] = false ;

        }

}

 

inline int gcd( int x , int y ) {

        if ( x < y ) swap( x , y ) ;

        for ( int z ; y ; z = y , y = x % y , x = z ) ;

        return x ;

}

 

struct NUM {

        int cnt[ maxn ] ;

        NUM(  ) {

                memset( cnt , 0 , sizeof( cnt ) ) ;

        }

        inline void add( int x ) {

                for ( int i = 0 ; i ++ < pn ; ) if ( x == 1 ) break ; else

                while ( ! ( x % p[ i ] ) ) {

                        ++ cnt[ i ] , x /= p[ i ] ;

                }

        }

} n1 , n2 ;

 

struct Bignum {

        int n , a[ maxn ] ;

        inline void Init(  ) {

                memset( a , 0 , sizeof( a ) ) ; a[ n = 1 ] = 1 ;

        }

        inline void mul( int x ) {

                for ( int i = 0 ; i ++ < n ; ) a[ i ] *= x ;

                for ( int i = 0 ; i ++ < n ; ) if ( a[ i ] >= 10 ) {

                        a[ i + 1 ] += a[ i ] / 10 ; a[ i ] %= 10 ;

                }

                while ( a[ n + 1 ] ) {

                        ++ n ;

                        if ( a[ n ] >= 10 ) {

                                a[ n + 1 ] += a[ n ] / 10 ; a[ n ] %= 10 ;

                        } else break ;

                }

        }

        inline void write(  ) {

                for ( int i = n ; i ; -- i ) printf( "%d" , a[ i ] ) ;

        }

} m ;

 

inline void print( NUM &x ) {

        m.Init(  ) ;

        for ( int i = 0 ; i ++ < pn ; ) for ( int j = 0 ; j ++ < x.cnt[ i ] ; ) {

                m.mul( p[ i ] ) ;

        }

        m.write(  ) ;

}

 

int n , t , d , a[ maxn ] , y[ maxn ] ;

 

int main(  ) {

        Init(  ) ;

        scanf( "%d%d%d" , &t , &n , &d ) ;

        int tot = 0 ;

        for ( int i = 0 ; i ++ < t ; ) {

                scanf( "%d" , a + i ) ; tot += a[ i ] ;

        }

        int x ; for ( int i = 0 ; i ++ < n ; ) scanf( "%d%d" , &x , y + i ) ;

        for ( int i = 0 , g , px , py ; i ++ < n ; ) {

                px = a[ y[ i ] ] , py = tot ; g = gcd( px , py ) ;

                px /= g , py /= g ; n1.add( px ) , n2.add( py ) ;

                a[ y[ i ] ] += d , tot += d ;

        }

        for ( int i = 0 ; i ++ < pn ; ) if ( n1.cnt[ i ] && n2.cnt[ i ] ) {

                if ( n1.cnt[ i ] > n2.cnt[ i ] ) {

                        n1.cnt[ i ] -= n2.cnt[ i ] ; n2.cnt[ i ] = 0 ;

                } else {

                        n2.cnt[ i ] -= n1.cnt[ i ] ; n1.cnt[ i ] = 0 ;

                }

        }

        print( n1 ) ; printf( "/" ) ; print( n2 ) ; printf( "\n" ) ;

        return 0 ;

}