poj2429 GCD LCM Inverse 数论 质因数分解

题意:输入两个数分别为 c , d
找到最小的 a + b
使得 Gcd(a,b) = c ; Lcm(a,b) = d;
找到 这样 的 a 与 b ,使得 a+b最小,而且要让 a<=b.
分析:
令 gcd(a,b) = c ,lcm(a,b) = d.
分析gcd与lcm的性质,有
gcd(a,b) * lcm(a,b) = a * b;
也就是 c * d = a * b,等式两边同时除以 c.
有 (d/c) = (a/c) * (b/c);
令 C = (d/c) , x1 = (a/c) ,x2 =(b/c) ,其中 x1与x2显然是互素的,因为它们都除以了彼此的最大公约数.
现在我们的目标是 找到x1 * x2 =C 而且x1+ x2最小.
一种显然的想法是,当且仅当x1 == x2时 ,x1 +x2 最小.
也就是x1 与 x2是尽量靠近 $$\sqrt{C}$$
那么直接去暴力枚举它附近的约数不就好了吗.
枚举代码,其中mid就是 sqrt( C ).

for(ll fac = mid ; fac>=1;fac--){if(C % fac ==0) {ans1 = fac;break;}}for(ll fac = mid;fac <=C;fac++){if(C%fac ==0){ans2 = fac;break;}}

不幸的是,这种做法超时了,因为数字太大了,可能枚举了很长一段的数字都没有出现约数导致超时,迫使我们放弃这种思路.
回到该式子:x1 * x2 =C 其中x1,x2互素.那么是否可以直接枚举x1与x2呢?
因为x1与x2是互素的,意味着C分解出来的质因数次数要全部选取完毕
比如说 $$C=2^3\ast 3^2\ast 5^4$$
可能的组合有$$x1=2^3,x2=3^2\ast 5^4$$
$$x1=2^3\ast 3^2,x2=5^4$$
$$x1=2^3\ast 3^2\ast 5^4,x3=1$$
就是若x1中含有了某个素数因子,那么就要把它的指数全部取完,否则x2也会含有该素数因子,
使得x1与x2不满足互素的情况.
那么思路已经很显然了,对于每个素数因子,只有拿与不拿两种决策,让我们考虑下C的数据范围下最多会有多少个素数因子.
暴力地把前23个素数相乘,得到的结果大约是$10^{29}$级别,早已超过了long long范围数.
而二进制枚举可以接受的复杂度是26左右,显然已经可以满足本题（n<23）的要求.
做法:
对 C进行质因数分解,算法使用Pollard - Rho.然后二进制枚举出所有的因数,找到最小的
x1 + x2. 最后结果输出 x1 * c + x2 * c.注意要让x1<x2.
最后,不要忘了对C=1的情况进行特判,因为Pollard -Rho算法不能接受C=1的情况.
Ac代码,用时47ms.

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 3e5+2;
const ll INF = 1e18;
const ll MOD = 1e18;
int prime[10]={2,3,5,7,11,13,19,61,29,37};
struct Prime{ll f_mul(ll x,ll y,ll mod){return ( x * y - (ll) ( (long double) x / mod*y )*mod + mod ) % mod;}ll f_pow(ll a,ll b,ll mod){ll ans = 1;while(b){if(b&1) ans= f_mul(ans,a,mod);b>>=1;a = f_mul(a,a,mod);}return ans%mod;
}ll gcd(ll a,ll b){if(b==0) return a;return gcd(b,a%b);}bool check(ll p,ll x){// to check  whether x is a prime.if(x % p ==0) return false;ll k = x - 1;ll t = f_pow(p%x,k,x);if(t!=1) return false;while(!(k&1)){ //一直到 k不是奇数为止 t = f_pow(p,k>>=1,x);if(t!=1&&t!=x-1) return false;if(t==x-1) return true;// t =x -1 而不是1的情况下 不能继续套用二次探索// 因为 x ^2  ≡1 是二次探索的右边 这时候右边是 x - 1 不能继续用了 认为通过测试. }return true;}bool Miller_Rabin(ll x){for(int i=0;i<10;i++){if(prime[i]==x) return true;if(!check(prime[i],x)) return false;}return true;}vector<ll> div;//储存分解之后的质因数 是无序的  需要进行处理.map<ll,int> div_cnt;//质因数的次数vector<ll> vec; ll ABS(ll x){return x>=0 ? x : (-x) ;}ll dfs(ll n){ll x1 = 0 , x2 =0, c= rand()%(n-1) + 1;ll val = 1;for(ll i=1;;i<<=2,x1=x2,val=1){for(ll j = 1;j<=i;++j){x2 = (f_mul(x2,x2,n)+c)%n;val =(f_mul(val,ABS(x1-x2),n))%n;if(j%127==0){ll d = gcd(val,n);if(d>1) return d;}}ll d = gcd(val,n);if(d>1) return d;}}void fac(ll n){if(n<2) return ;if(Miller_Rabin(n)) {div.push_back(n); return ;}ll p = n;while(p>=n) p = dfs(n);while(n%p==0) n/=p;fac(n);fac(p);}void pollard(ll n){fac(n);sort(div.begin(),div.end());div.erase(unique(div.begin(),div.end()),div.end());for(vector<ll>::iterator it=div.begin();it!=div.end();it++){while(n%(*it)==0) n/=(*it),div_cnt[(*it)]++;}for(vector<ll>::iterator it = div.begin();it!=div.end();it++){vec.push_back(f_pow((*it),div_cnt[(*it)],MOD));}}
};
int main(){ll c,d;Prime p;while(scanf("%lld %lld",&c,&d)==2){p.div.clear();p.div_cnt.clear();p.vec.clear();ll C = d / c;if(C==1){//特判  c =d的情况  cout<<c<<" "<<c<<"\n";continue;}p.pollard(C);//质因数分解vector<ll> &vec = p.vec;int n = vec.size();ll ans=INF,ans1,ans2;for(int s = 1 ;s<(1<<n);s++){ll ans_t1=1,ans_t2=1;for(int i=0;i<n;i++){if( s&(1<<i) ) ans_t1*=vec[i];    }ans_t2 = C/ans_t1;if(ans_t1+ans_t2<ans) {ans1=ans_t1,ans2=ans_t2;ans = ans_t1+ans_t2;}
}
if(ans1>ans2) swap(ans1,ans2);cout<<ans1*c<<" "<<ans2*c<<"\n";
}
return 0;}