- UVA 10375
- UVA 10791
UVA10375 Choose and divide
题解
先素数打表，然后用唯一分解定理，将素数的指数存到数组e中即可
代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn = 10000 + 5;
vector< int > primes;
int vis[ maxn ], e[ maxn ], siz;
void get_prime()
{
int m = floor( sqrt( 10000 ) + 0.5 );
for( int i = 2; i <= m; i ++ )
{
if( !vis[ i ] )
{
for( int j = i * i; j <= 10000 ;j += i ) vis[ j ] = 1;
}
}
for( int i = 2; i <= 10000; i ++ )
{
if( !vis[ i ] ) primes.push_back( i );
}
}
void get_e( int n, int m )
{
for( int i = 0; i < siz; i ++ )
{
while( n % primes[ i ] == 0 )
{
e[ i ] += m;
n /= primes[ i ];
}
if( n == 1 ) break;
}
}
void add_integer( int n, int m )
{
for( int i = 2; i <= n; i ++ ) get_e( i, m );
}
int main()
{
get_prime();
siz = primes.size();
int p, q, r, s;
while( ~scanf( "%d%d%d%d", &p, &q, &r, &s ) )
{
memset( e, 0, sizeof( e ) );
add_integer( p, 1 );
add_integer( s, 1 );
add_integer( r - s, 1 );
add_integer( q, -1 );
add_integer( p - q, -1 );
add_integer( r, -1 );
double goal = 1.0;
for( int i = 0; i < siz; i ++ ) goal *= pow( primes[ i ], e[ i ] );
printf( "%.5f\n", goal );
}
return 0;
}
