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