POJ 2429 GCD & LCM Inverse(大整数素因子分解+二进制枚举)

xiaoxiao2021-02-28  10

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


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.


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.


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


已知两个数的最大公约数 值为 a a a, 最小公倍数值为 b b b,现在求这两个数使得两个数的和最小,输出这两个数。


假设这两个数字为 x , y x, y x,y,那么有 { G C D ( x , y ) = a L C M ( x , y ) = b \begin{cases} GCD(x,y)=a\\LCM(x,y)=b \end{cases} {GCD(x,y)=aLCM(x,y)=b 其中 L C M ( x , y ) = x ∗ y G C D ( x , y ) = x ∗ y a LCM(x,y)=\frac {x*y}{GCD(x,y)}=\frac{x*y}a LCM(x,y)=GCD(x,y)xy=axy 那么就有 \begin{align} n&=\frac x{gcd(x,y)}*\frac y{gcd(x,y)}\ &=\frac{lcm(x,y)}{gcd(x,y)}\ &=\frac b a \end{align} 那么 n n n 一定是两个互素的数的乘积,假设为 a a , b b aa, bb aa,bb,那么我们只要解使得 a a + b b aa+bb aa+bb 值最小的 a a , b b aa,bb aa,bb 就OK了,最后在乘以 g c d ( x , y ) gcd(x,y) gcd(x,y) 就是结果。 那么我们首先将 n n n 进行素因子分解,但现在 n n n 是一个比较大的数,所以就要用到大因数分解 p o l l a r d _ r h o pollard\_rho pollard_rho,因数分解之后假设: n = p 1 a 1 ∗ p 2 a 2 ∗ . . . ∗ p k a k n={p_1}^{a_1}*{p_2}^{a_2}*...*{p_k}^{a_k} n=p1a1p2a2...pkak 那么我们需要保证的是两个数是互素的,所以两个数不能出现相同素因子,那么我们可以进行二进制枚举,判断这个素因子在 a a aa aa 中是否存在,然后找到 a a + b b aa+bb aa+bb 最小的 a a , b b aa,bb aa,bb


#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; }
转载请注明原文地址: https://www.6miu.com/read-1100239.html