大整数素性测试和因子分解

大整数素性测试和因子分解

照着算导打就完了

By Rapiz 2019-09-15

算导的 Pollard Rho 不保证能运行成功。如果出现 d == n 的情况，则直接返回n，说明分解失败，需要再次调用。详情看代码

/*
 *     ____              _    
 *    / __ \____ _____  (_)___
 *   / /_/ / __ `/ __ \/ /_  /
 *  / _, _/ /_/ / /_/ / / / /_
 * /_/ |_|\__,_/ .___/_/ /___/
 *            /_/             
 *           code@rapiz.me
 *          Sat, 14 Sep 2019 09:10:57 +0800
 */
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <map>
#include <vector>
#include <utility>
#include <cassert>
#include <string>
#define xxx(x) cerr<<(#x)<<": "<<x<<endl;
#define fastios ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
using namespace std;
ll a, b;
ll gcd(ll a, ll b) {a=a>0?a:-a;b=b>0?b:-b;return b ? gcd(b, a%b) : a;}
inline ll qmul(ll a, ll b, ll mod) {
  ll d = (ll)floor(a*(long double)b/mod + 0.5);
  ll ret = a*b - d*mod;
  if (ret < 0) ret += mod;
  return ret;
}
inline ll randint(ll l, ll r) {
  return (((ll)rand())^rand())%(r - l + 1) + l;
}
ll qpow(ll x, ll r, ll mod) {
  ll ret = 1;
  for(ll tmp = x; r; r>>=1) {
    if (r&1) ret = qmul(ret, tmp, mod);
    tmp = qmul(tmp, tmp, mod);
  }
  return ret;
}
bool witness(ll a, ll n) {
  int t;
  ll m;
  for (t = 0, m = n - 1; m && !(m&1);t++, m>>=1) ;
  ll x = qpow(a, m, n);
  for (int i = 1; i <= t; i++) {
    ll nx = qmul(x, x, n);
    if (nx == 1 && x != 1 && x != n - 1) return true;
    x = nx;
  }
  return x != 1;
}
bool primetest(ll n) {
  if (n == 1) return false;
  const int s = 20;
  for (int i = 1; i <= s; i++) {
    ll a = randint(1, n - 1);
    if (witness(a, n)) return false;
  }
  return true;
}
ll rho(ll n) {
  if (n == 1) return 1;
  else if (n == 0) return 0;
  ll i, k;
  ll x, y, c;
  for (i = 2, x = randint(0, n - 1), y = x, k = 2, c = rand(); 1; i++) {
    x = (qmul(x, x, n) + c)%n;
   ll d = gcd(y - x, n);
    if (d > 1) {
      return d;
    }
    if (i == k) k<<=1, y = x;
  }
}
map<ll, int> mm;
void resolve(ll n) {
  if (n == 1) return;
  if (primetest(n)) {
    mm[n]++;
  }
  else {
    ll p = n;
    while (p == n) {
      p = rho(p);
    }
    resolve(p);
    resolve(n/p);
  }
}
vector<pair<ll, int> > fac;
double sum;
ll ans;
void dfs(int idx, ll x) {
  if (b/x + x < sum) {
    sum = b/x + x;
    ans = x;
  }
  if (idx >= (int)fac.size()) return;
  dfs(idx+1, x);
  for (ll i = 1; i <= fac[idx].second; i++, x *= fac[idx].first);
  dfs(idx+1, x);
}
void solve() {
  mm.clear();
  fac.clear();
  sum = 1e20;
  b /= a;
  ans=1;
  resolve(b);
  for (map<ll, int>::iterator x = mm.begin(); x != mm.end(); x++) {
    fac.push_back(*x);
  }
  dfs(0, 1);
  if (b/ans > ans) ans = b/ans;
  cout << (b/ans*a) << " " << (ans*a) << " "<<endl;
}
int main() {
  //srand(time(NULL));
  fastios;
  while (cin >> a >> b) {
    solve();
  }
}