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