# POJ 2429 GCD &amp; LCM Inverse（大整数素因子分解+二进制枚举）

xiaoxiao2021-02-28  10

GCD & LCM Inverse Time Limit: 2000MSMemory Limit: 65536KTotal Submissions: 16540Accepted: 3061

Description

Given two positive integers a and b, we can easily calculate the greatest common divisor (GCD) and the least common multiple (LCM) of a and b. But what about the inverse? That is: given GCD and LCM, finding a and b.

Input

The input contains multiple test cases, each of which contains two positive integers, the GCD and the LCM. You can assume that these two numbers are both less than 2^63.

Output

For each test case, output a and b in ascending order. If there are multiple solutions, output the pair with smallest a + b.

Sample Input

3 60

Sample Output

12 15

#include <iostream> #include <string.h> #include <string> #include <algorithm> #include <stdio.h> #include <stdlib.h> #include <math.h> #include <map> using namespace std; typedef long long LL; const int times=20;//随机算法判定次数 map <LL, int>mp;//质因子的数目 LL Multi(LL a, LL b, LL MOD){ LL ans = 0; while(b){ if(b & 1) ans = (ans + a) % MOD; b>>=1; a = (a + a) % MOD; } return ans; } LL Pow(LL a, LL b, LL MOD){ a = a % MOD; LL ans = 1; while(b){ if(b & 1) ans = Multi(ans, a, MOD); b>>=1; a = Multi(a, a, MOD); } return ans; } //若为合数返回true，不一定返回false //a^(n-1)=1(mod n) -> a^((2^t)*x)=-1(mod n) == a^x=1(mod n) bool test(LL a,LL n,LL x,LL t)//miLLer_rabin算法的核心 { LL res = Pow(a,x,n);//a^x mod n LL last = res; for(int i=1;i<=t;i++){ res=Multi(res,res,n);//res=res*res mod n if(res==1 && last!=1 && last!=n-1) return true; last=res; } if(res!=1) return true; return false; } //若为素数（或伪素数）返回true，合数返回false bool miLLer_rabin(LL n){ if(n < 2) return false; if(n==2) return true; if((n&1)==0) return false; //偶数 LL x=n-1, t=0; while((x&1)==0)//n-1=(2^t)*x; { x>>=1; t++; } for(int i=0;i<times;i++)//进行随机判定 { LL a=rand()%(n-1)+1;//随机找0~n-1的整数 if(test(a,n,x,t)) return false; } return true; } LL factor[100];//保存质因数分解结果 int tot;//记录质因数个数，下标从0开始 LL GCD(LL a, LL b){ if(a < 0) return GCD(-a, b); if(b == 0) return a; return GCD(b, a%b); } LL pollard_rho(LL x,LL c){ LL i=1,k=2; LL x0=rand()%x; LL y=x0; while(1){ i++; x0=(Multi(x0,x0,x)+c)%x; LL d=GCD(y-x0,x); if(d!=1&&d!=x) return d; if(y==x0) return x; if(i==k){ y=x0; k+=k; } } } //对n进行素因子分解 void find_factor(LL n){ if(miLLer_rabin(n))//若为素数 { factor[tot++]=n; mp[n]++; return ; } LL p=n; while(p>=n) p=pollard_rho(p,rand()%(n-1)+1); find_factor(p); find_factor(n/p); } LL pw(LL a, LL b){ LL ans = 1; while(b){ if(b & 1) ans = ans*a; b>>=1; a*=a; } return ans; } int main(){ LL a, b; while(cin>>a>>b){ if(a==b){printf("%lld %lld\n",a,b); continue;} tot = 0; mp.clear(); LL n = b/a; find_factor(n); sort(factor, factor+tot); tot = unique(factor, factor+tot)-factor; LL ans = (1ll<<63)-1, aa, bb; int all = (1<<tot); for(int i=0; i<all; i++){ LL tp1 = 1, tp2 = 1; for(int j=0; j<tot; j++){ if(i&(1<<j)){ LL tmp = pw(factor[j] , mp[factor[j]]); tp1 *= tmp; } } tp2 = n / tp1; if(ans > tp1*a+tp2*a){ ans = tp1*a+tp2*a; aa = min(tp1, tp2); bb = max(tp1, tp2); } } printf("%lld %lld\n",aa*a, bb*a); } return 0; }