| ||||||||||
| 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 | |||||||||
用C++就AC,换成G++就RE???#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <string>
#include <sstream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <climits>
#include <ctime>
#include <bitset>
#include <functional>
#ifdef __APPLE__
FILE *__fp = fopen("__sample.in", "r");
#define scanf(...) fscanf(__fp, __VA_ARGS__)
#define cin fin
std::ifstream cin("__sample.in");
#endif
using namespace std;
typedef pair<int, int> ii;
typedef long long ll;
typedef unsigned long long ull;
const int INT_INF = 0x3f3f3f3f, INT_NINF = 0xc0c0c0c0;
const int d4r[] = {0, 1, 0, -1}, d4c[] = {1, 0, -1, 0};
const int mxnf = 100;
const int witness[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
const int sz_witness = 12;
const ull A_MAX = 1ULL << 32;
int nf;
ull factor[mxnf];
ull rest[mxnf];
ull best;
ull mul(ull a, ull b, ull p) {
ull ret = 0;
for (ull base = a; b; b >>= 1) {
if (b & 1) {
ret = (ret + base) % p;
}
base = (base + base) % p;
}
return ret;
}
bool ptest(ull p) {
ull d = p - 1;
while (!(d & 1)) d >>= 1;
for (int i = 0; i < sz_witness && witness[i] < p; i++) {
ull a = witness[i], r = 1;
for (ll dd = d; dd; dd >>= 1, a = mul(a, a, p)) {
if (dd & 1) r = mul(r, a, p);
}
if (r == 1) goto success;
for (ll dd = d; dd < p - 1; dd <<= 1, r = mul(r, r, p)) {
if (r == p - 1) goto success;
}
return false;
success:;
}
return true;
}
ull __gcd(ull a, ull b) {
ull tmp;
while (b) {
tmp = a; a = b; b = tmp % b;
}
return a;
}
ull pollard_rho(ull n) {
while (!ptest(n)) {
while (true) {
ull fast = rand() % 10000, slow = fast, p = 1, c = rand() % 100;
while (p == 1) {
slow = (mul(slow, slow, n) + c) % n;
fast = (mul(fast, fast, n) + c) % n;
fast = (mul(fast, fast, n) + c) % n;
p = __gcd(fast < slow ? slow - fast : fast - slow, n);
}
if (p < n) {
return pollard_rho(p);
}
}
}
return n;
}
ull brent_rho(ull n) {
while (!ptest(n)) {
while (true) {
ull y = rand() % 10000, x = y, p = 1, c = rand() % 100;
for (ull len = 1; p == 1; len <<= 1) {
y = x, p = 1;
for (ull i = 0; i < len && p == 1; i++) {
x = (mul(x, x, n) + c) % n;
p = __gcd(x < y ? y - x : x - y, n);
}
if (1 < p && p < n) return brent_rho(p);
}
}
}
return n;
}
void dfs(int i, ull cur, ull n) {
if (cur >= A_MAX || cur * cur > n || cur * rest[i] <= best) return;
best = max(best, cur);
if (i == nf) return;
dfs(i + 1, cur, n);
dfs(i + 1, cur * factor[i], n);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ull gcd, lcm;
while (cin >> gcd >> lcm) {
ull N = lcm / gcd, n = N;
nf = 0;
for (int i = 0; i < sz_witness; i++) {
ull p = witness[i];
if (n % p == 0) {
ull r = 1;
for (; n % p == 0; n /= p) r *= p;
factor[nf++] = r;
}
}
for (; n > 1; nf++) {
ull p = brent_rho(n);
ull r = 1;
for (; n % p == 0; n /= p) r *= p;
factor[nf] = r;
}
rest[nf] = 1;
for (int i = nf - 1; i >= 0; i--) {
rest[i] = rest[i + 1] * factor[i];
}
best = 1;
dfs(0, 1, N);
cout << best * gcd << " " << N / best * gcd << endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator