POJ - 2429 GCD & LCM Inverse（Pollard_rho质因数分解+搜索）

传送门

题目大意：

给出两个数的 $gcd,lcm$，问这两个数为多少时使得二者的和最小

分析：

根据最大公因数的性质，两个数的 $gcd$为其相同质因子指数的 $min$；同理最小公倍数的性质，两个数的 $lcm$为其相同质因子指数的 $max$。那么显然我们对 $gcd,lcm$分别质因数分解，最后操作分解出来的 $lcm$中不同的质因子，然后 $dfs$求出最小的 $a+b$

显然分解两个数太麻烦了，因为 $lcm$含有 $gcd$的所有质因子，且个数一定是大于等于的，那么我们只需要对 $lcm/gcd$分解质因数，然后求出的结果分解乘一个 $gcd$

吐槽一波，这题快速乘wa了十几发，多次仔细对比网上题解，改了龟速乘就过了，无语

//
// Created by Happig on 2020/8/18
//
#include <cstdio>
#include <math.h>
#include <map>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <iostream>using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x, y) make_pair(x,y)
#define mem(a, x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double dinf = 1e300;
const ll INF = 1e18;
const int Mod = 1e9 + 7;
const int maxn = 1e4 + 10;struct BigIntegerFactor {const static int maxm = 1e6 + 10;ll prime[maxm], p[maxm], sz, cnt;ll fac[10010], num[10010];// inline ll mul(ll a, ll b, ll p) { //wa了尝试下面的慢速乘或者改为__int128
// if (p <= 1000000000) return a * b % p;
// else if (p <= 1000000000000LL) return (((a * (b >> 20) % p) << 20) + (a * (b & ((1 << 20) - 1)))) % p;
// else {
// ll d = (ll) floor(a * (long double) b / p + 0.5);
// ll ret = (a * b - d * p) % p;
// if (ret < 0) ret += p;
// return ret;
// }
// }inline ll mul(ll a, ll b, ll Mod) {ll ans = 0;while (b) {if (b & 1) ans = (ans + a) % Mod;a = (a + a) % Mod;b >>= 1;}return ans;}void init(int up) {  //传入的参数不能超过maxm,根据数据范围来定,1e5wa了就改1e6试试int tot = 0;sz = up - 1;for (int i = 1; i <= sz; i++) p[i] = i;for (int i = 2; i <= sz; i++) {if (p[i] == i) prime[tot++] = i;for (int j = 0; j < tot && 1LL * i * prime[j] <= sz; j++) {p[i * prime[j]] = prime[j];if (i % prime[j] == 0) break;}}}inline ll qkp(ll x, ll n, ll p) {ll ans = 1;while (n) {if (n & 1) ans = mul(ans, x, p);x = mul(x, x, p);n >>= 1;}return ans;}inline bool check(ll a, ll n) {ll t = 0, u = n - 1;while (!(u & 1)) t++, u >>= 1;ll x = qkp(a, u, n), xx = 0;while (t--) {xx = mul(x, x, n);if (xx == 1 && x != 1 && x != n - 1) return false;x = xx;}return xx == 1;}inline bool miller(ll n, ll k) {  //检测一个数n是否为素数,一般k取20即可if (n == 2) return true;if (n < 2 || !(n & 1)) return false;if (n <= sz) return p[n] == n;for (int i = 0; i <= k; i++) {if (!check(rand() % (n - 1) + 1, n)) return false;}return true;}inline ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}inline ll Abs(ll x) {return x < 0 ? -x : x;}inline ll Pollard_rho(ll n) {ll s = 0, t = 0, c = rand() % (n - 1) + 1, v = 1, ed = 1;while (1) {for (int i = 1; i <= ed; i++) {t = (mul(t, t, n) + c) % n;v = mul(v, Abs(t - s), n);if (i % 127 == 0) {ll d = gcd(v, n);if (d > 1) return d;}}ll d = gcd(v, n);if (d > 1) return d;s = t, v = 1, ed <<= 1;}}void getfactor(ll n) {  //得到有重复的质因子if (n <= sz) {while (n != 1) fac[cnt++] = p[n], n /= p[n];return;}if (miller(n, 6)) fac[cnt++] = n;else {ll d = n;while (d >= n) d = Pollard_rho(n);getfactor(d);getfactor(n / d);}}void print(ll x) {   //打印"质因子-个数"cnt = 0;getfactor(x);int k = 1;num[0] = 1;sort(fac, fac + cnt);for (int i = 1; i < cnt; i++) {if (fac[i] == fac[i - 1])num[k - 1]++;else {num[k] = 1;fac[k++] = fac[i];}}cnt = k;for (int i = 0; i < cnt; i++)printf("%lld %lld\n", fac[i], num[i]);}void solve(ll x, ll &tot) {  //进行其他操作cnt = 0;getfactor(x);ll k = 1;num[0] = 1;sort(fac, fac + cnt);for (int i = 1; i < cnt; i++) {if (fac[i] == fac[i - 1])num[k - 1]++;else {num[k] = 1;fac[k++] = fac[i];}}cnt = tot = k;}} Q;ll fac[maxn], num[maxn];
ll g, l, res, ansa, ansb, sum, tot;ll qkp(ll x, ll n) {ll ans = 1;while (n) {if (n & 1) ans *= x;x *= x;n >>= 1;}return ans;
}ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);
}void dfs(ll a, ll b, ll deep) {if (a * g + b * g > sum) return;if (deep == tot) {if (sum > a * g + b * g) {sum = a * g + b * g;ansa = a * g, ansb = b * g;}return;}dfs(a * fac[deep], b, deep + 1);dfs(a, b * fac[deep], deep + 1);
}int main() {//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);//ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);Q.init(100000);while (~scanf("%lld%lld", &g, &l)) {if (g == l) {printf("%lld %lld\n", g, l);continue;}//Q.solve(g, tot1, fac1, num1);//Q.print(l/g);res = l / g;Q.solve(res, tot);memcpy(fac, Q.fac, sizeof Q.fac);memcpy(num, Q.num, sizeof Q.num);for (int i = 0; i < tot; i++)fac[i] = qkp(fac[i], num[i]);sum = INF;dfs(1LL, 1LL, 0);if (ansa > ansb) swap(ansa, ansb);printf("%lld %lld\n", ansa, ansb);}return 0;
}