| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
wa了一整天,n个因子相乘算成了n个因子相加,QAQ, 贴份ac代码#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <time.h>
#define ll long long
#define ull unsigned long long
#define rep( i, a, n ) for( ull i = a; i < n; i++ )
#define per( i, a, n ) for( ull i = n - 1; i >= a; i-- )
#define mem( f, x ) memset( f, x, sizeof( f ) )
#define pii pair<int, int>
#define fi first
#define se second
#define MOD 8191
#define INF 0x3f3f3f3f
#define e 2.71828
using namespace std;
const int N = 100;
const int M = 150;
const int MAX = 5;
const ull inv = 500000004;
const double g = 9.80;
const double PI = acos( -1.0 );
ull s = 20, cnt, ct;
ull A, B;
ull num[N], su[N];
ull ans;
ull gcd( ull a, ull b ){
return b==0?a:gcd( b, a%b );
}
ull q_mul( ull x, ull y, ull mod ){
x %= mod, y %= mod;
ull ret = 0;
while( y ){
if( y&1 ) ret = ( ret + x ) % mod;
x = ( x + x ) % mod;
y >>= 1;
}
return ret;
}
ull q_pow( ull x, ull y, ull mod ){
if( y == 0 ) return 1ull;
x %= mod;
if( y == 1 ) return x;
ull ret = 1;
while( y ){
if( y&1 ) ret = q_mul( ret, x, mod );
x = q_mul( x, x, mod );
y >>= 1;
}
return ret;
}
bool Judge( ull x, ull y, ull p , ull t ){
ull ret = q_pow( x, y, p );
ull pre = ret;
rep( i, 0, t ){
ret = q_mul(ret, ret, p );
if( ret == 1 && pre != 1 && pre != p-1 )
return 1;
pre = ret;
}
if( ret != 1 ) return 1;
return 0;
}
bool miller( ull n ){
if( n <2 ) return 0;
if( n == 2 ) return 1;
if( (n&1) == 0 ) return 0;
ull mod = n -1, t = 0;
while( ( mod & 1 ) == 0 ) t++, mod>>=1;
srand(( ull )12234336);
rep( i, 0, s ){
ull x = rand( ) % ( n - 2 ) + 2;
if( Judge( x, mod, n, t ) )
return 0;
}
return 1;
}
ull Floyed( ull n, ull c ){
ull i = 1, j = 2;
ull x = rand() % ( n -1 ) + 1, y = x;
while( 1 ){
i++;
x = ( q_mul( x, x, n ) + c ) % n;
ull p = gcd(( y - x + n ) % n, n );
if( p != 1 && p != n )
return p;
if( x == y ) return n;
if( i == j ) y = x, j <<= 1;
}
}
void Find( ull n, ull c ){
if( n == 1 ) return;
if( miller(n) ){
num[cnt++] = n;
return;
}
ull x = n, k = c;
while( x == n ) x = Floyed( x, c-- );
Find( n/x, k );
Find( x, k );
}
void dfs( ull st, ull cmt, ull sum, ull c, ull x ){
if( sum * sum > x ) return;
if( cmt == c ){
ull tp = x / sum;
if( ans > tp + sum ){
ans = tp + sum;
A = sum, B = tp;
if( A > B ) swap( A, B );
}
return;
}
for( ull i = st + 1; i <= ct; i++ ){
dfs( i, cmt + 1, sum * su[i], c, x );
}
}
int main( ){
ull m, n;
while( scanf( "%lld %lld", &m, &n ) != EOF ){
mem( num, 0 );
if( m == n ){
printf( "%lld %lld\n", m, n );
continue;
}
ull tmp = n / m;
cnt = 1, ans = ( 1ull<<62 );
Find( tmp, 180 );
sort( num + 1, num + cnt );
ull pre = num[1];
su[1] = num[1], ct = 1;
rep( i, 2, cnt ){
if( num[i] != pre )
pre = num[i], su[++ct] = num[i];
else
su[ct] *= num[i];
}
if( ct == 1 ){
printf( "%lld %lld\n", m, n );
continue;
}
rep( i, 1, ct )
dfs( 0, 0, 1, i, tmp );
printf( "%lld %lld\n", A*m, B*m );
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator