题意给出最大公约数和最小公倍数,让求出满足这个条件的两个数并且该两个数的和最小。并按照从小到大的顺序输出。因子分解用的是Pollard rho启发式方法
首先给出了gcd lcm,令两个数为ansm*gcd ansn*gcd,那么lcm=(ansm*gcd)*(ansn*gcd)/gcd=ansm*gcd*ansn,那么ansn*ansm=lcm/gcd,所以将lcm/gcd进行因子分解所得到的因子一部分乘积为ansm,那么剩下的就是ansn,并且ansn ansm互素(如果不互素那么两个数的最大公约数就不是给出的gcd了),所以枚举所有的互素的 ansn ansm,找出ansn ansm和最小的情况就行,再将两数乘gcd还原,注意从小到大输出,两数相等直接输出两个数。
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; typedef long long int64; int64 m,n,ansn,ansm; int64 gcd(int64 a,int64 b) { if (a==0) return 1; if(a<0) return gcd(-a,b); if(b==0) return a; return gcd(b,a%b); } int64 modmult(int64 a,int64 b,int64 n)//a*b%n { a%=n; int64 ret; for(ret=0; b; a=(a<<1)%n,b>>=1) if(b&1) ret=(ret+a)%n; return ret; } int64 modular(int64 a,int64 b,int64 n)//renturn a^b%n { int64 ans=1; a%=n; while(b) { if(b&1) ans=modmult(ans,a,n),b--; b>>=1; a=modmult(a,a,n); } return ans; } bool witness(int64 a,int64 n)//判断 a^(n-1)=1(mod n) { int t=0; int64 x,xi,temp=n-1; while(temp%2==0) t++,temp/=2; xi=x=modular(a,temp,n); for(int i=1; i<=t; i++) { xi=modmult(xi,xi,n); if(xi==1&&x!=1&&x!=n-1) return 1; x=xi; } if(xi!=1) return 1; return 0; } bool millar_rabin(int64 n,int s) { for(int j=1; j<=s; j++) { int64 a=rand()%(n-1)+1;//a=rand()%(Y-X+1)+X; /*n为X~Y之间的随机数 if(witness(a,n)) return 0; } return 1; } int64 pollard_rho(int64 n,int64 c) { int64 i=1,k=2,x,y; x=rand()%n; y=x; while(1) { i++; x=(modmult(x,x,n)+c)%n; int64 d=gcd(y-x,n); if(d!=1&&d!=n) return d; if(x==y) return n; if(i==k) { y=x; k+=k; } } } int64 factor[1000]; int tol; void findfac(int64 n) { if(millar_rabin(n,10)) { factor[tol++]=n; return; } int64 p=n; while(p>=n) p=pollard_rho(p,rand()%(n-1)+1); findfac(p); findfac(n/p); } void dfs(int64 s,int64 now) { if(s==tol) { if(gcd(now,m/now)==1&&now+m/now<ansm+ansn) ansm=now,ansn=m/now; return; } dfs(s+1,now*factor[s]); dfs(s+1,now); } int main() { int64 gcdx,lcm; while(~scanf("%lld%lld",&gcdx,&lcm)) { if(gcdx==lcm) { cout<<gcdx<<" "<<lcm<<endl; continue; } tol=0; lcm/=gcdx; findfac(lcm); m=n=1; sort(factor,factor+tol); for(int i=0; i<tol; i++) m*=factor[i]; ansn=n,ansm=m; dfs(0,1); if(ansn>ansm) swap(ansn,ansm); printf("%lld %lld\n",ansn*gcdx,ansm*gcdx); } return 0; }