GCD & LCM Inverse
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 16206   Accepted: 3008

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

Source

题意:
给出gcd和lcm求和最小的两个数a,b
代码:
//a*b=gcd*lcm,x=a/gcd,y=b/gcd,s=lcm/gcd => x*y=s;
//想要a+b小 => x*gcd+y*gcd小 => x+y小,x和y越接近sqrt(S)时x+y越小(对勾函数)
//所以求出s的素因子然后搞一搞就行了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<algorithm>
using namespace std;
typedef long long ll;
const int S=;//随机算法判定次数,S越大判错概率越小
//计算(a*b)%c;a,b,c<2^63
ll mult_mod(ll a,ll b,ll c){
a%=c;
b%=c;
ll ret=;
while(b){
if(b&){
ret+=a;
ret%=c;
}
a<<=;
if(a>=c) a%=c;
b>>=;
}
return ret;
}
//计算(x^n)%c
ll pow_mod(ll x,ll n,ll c){
if(n==) return x%c;
x%=c;
ll tmp=x;
ll ret=;
while(n){
if(n&) ret=mult_mod(ret,tmp,c);
tmp=mult_mod(tmp,tmp,c);
n>>=;
}
return ret;
}
//以a为基,n-1=x*2^t a^(n-1)=1(mod n) 验证n是不是合数
//一定是合数返回true,不一定返回false
bool check(ll a,ll n,ll x,ll t){
ll ret=pow_mod(a,x,n);
ll last=ret;
for(int i=;i<=t;i++){
ret=mult_mod(ret,ret,n);
if(ret==&&last!=&&last!=n-) return true;
last=ret;
}
if(ret!=) return true;
return false;
}
// Miller_Rabin()算法素数判定
//是素数返回true.(可能是伪素数,但概率极小)
//合数返回false;
bool Miller_Rabin(ll n){
if(n<) return false;
if(n==) return true;
if((n&)==) return false;
ll x=n-;
ll t=;
while((x&)==){
x>>=;
t++;
}
for(int i=;i<S;i++){
ll a=rand()%(n-)+;
if(check(a,n,x,t)) return false;
}
return true;
}
ll gcd(ll a,ll b){
if(a==) return ;
if(a<) return gcd(-a,b);
while(b){
ll t=a%b;
a=b;
b=t;
}
return a;
}
//Pollard_rho质因数分解算法
ll factor[];//质因数分解结果(无序的)
int tot;//质因数的个数,数组下标从0开始
ll Pollard_rho(ll x,ll c){
ll i=,k=;
ll x0=rand()%x;
ll y=x0;
while(){
i++;
x0=(mult_mod(x0,x0,x)+c)%x;
ll d=gcd(y-x0,x);
if(d!=&&d!=x) return d;
if(y==x0) return x;
if(i==k){
y=x0;
k+=k;
}
}
}
//对n进行素因子分解
void findfac(ll n){
if(Miller_Rabin(n)){//素数
factor[tot++]=n;
return;
}
ll p=n;
while(p>=n)
p=Pollard_rho(p,rand()%(n-)+);
findfac(p);
findfac(n/p);
}
ll ans,fa[];
int nu;
void dfs(int st,ll x,ll maxx)
{
if(st>nu){
if(x<=maxx&&x>ans)
ans=x;
return;
}
dfs(st+,x,maxx);
dfs(st+,x*fa[st],maxx);
}
int main()
{
//srand(time(NULL));
ll a,b;
while(scanf("%lld%lld",&a,&b)==){
if(a==b){
printf("%lld %lld\n",a,b);
continue;
}
tot=nu=;
ll s=b/a;
findfac(s);
sort(factor,factor+tot);
fa[]=factor[];
for(int i=;i<tot;i++){//合并相同的素因子
if(factor[i]==factor[i-]) fa[nu]*=factor[i];
else
fa[++nu]=factor[i];
}
ll x=(ll)sqrt(s*1.0);
ans=;
dfs(,,x);
printf("%lld %lld\n",ans*a,s/ans*a);
}
return ;
}

最新文章

  1. php知识案列分享
  2. python程序打包成.exe----pyinstaller工具
  3. Toast工具类,Android中不用再每次都写烦人的Toast了
  4. POJ1637 Sightseeing tour (混合图欧拉回路)(网络流)
  5. bzoj2049: [Sdoi2008]Cave 洞穴勘测
  6. 修复ubuntu播放wmv等视频没有声音问题
  7. hdu4858 项目管理 bestcoder round1 B
  8. MFS文件系统的组成
  9. 谷歌chrome 插件(扩展)开发——进阶篇(c#本地程序和插件交互)下
  10. java中内存的使用
  11. C#知识拾遗
  12. Ajax 与文件上传
  13. 小甲鱼Python第二十讲课后习题---021
  14. linux系统如何发送邮件
  15. jQuery $.ajax传递数组的traditional参数传递必须true
  16. db2look 工具
  17. git使用备注
  18. 如何用 Python 实现 Web 抓取?
  19. 20165302 程上杰 Exp2 后门原理与实践
  20. Python3之turtle模块的使用

热门文章

  1. 【第二章】Shell 变量
  2. 在本地电脑使用远程服务器的图形界面——包括 MATLAB、PyCharm 等各种软件
  3. Elasticsearch 评分score计算中的Boost 和 queryNorm
  4. ThinkPHP - 2 - SAE(新浪云)部署
  5. 6.azkban的监控
  6. 五:Edits Viewer离线日志查看器
  7. Python中的namespace package
  8. Java 集合框架之 Map
  9. JavaScript初探系列之面向对象
  10. dataTables工作总结