BZOJ-1498: [NOI2006]神奇的口袋
2019-03-15 本文已影响0人
AmadeusChan
题目：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 ;
}
