首页 > 代码库 > POJ 2429 long long 质因数分解
POJ 2429 long long 质因数分解
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
POJ Achilles
题意:
给出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=20;//随机算法判定次数,S越大判错概率越小//计算(a*b)%c;a,b,c<2^63ll mult_mod(ll a,ll b,ll c){ a%=c; b%=c; ll ret=0; while(b){ if(b&1){ ret+=a; ret%=c; } a<<=1; if(a>=c) a%=c; b>>=1; } return ret;}//计算(x^n)%cll pow_mod(ll x,ll n,ll c){ if(n==1) return x%c; x%=c; ll tmp=x; ll ret=1; while(n){ if(n&1) ret=mult_mod(ret,tmp,c); tmp=mult_mod(tmp,tmp,c); n>>=1; } return ret;}//以a为基,n-1=x*2^t a^(n-1)=1(mod n) 验证n是不是合数//一定是合数返回true,不一定返回falsebool check(ll a,ll n,ll x,ll t){ ll ret=pow_mod(a,x,n); ll last=ret; for(int i=1;i<=t;i++){ ret=mult_mod(ret,ret,n); if(ret==1&&last!=1&&last!=n-1) return true; last=ret; } if(ret!=1) return true; return false;}// Miller_Rabin()算法素数判定//是素数返回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; ll t=0; while((x&1)==0){ x>>=1; t++; } for(int i=0;i<S;i++){ ll a=rand()%(n-1)+1; if(check(a,n,x,t)) return false; } return true;}ll gcd(ll a,ll b){ if(a==0) return 1; if(a<0) return gcd(-a,b); while(b){ ll t=a%b; a=b; b=t; } return a;}//Pollard_rho质因数分解算法ll factor[1000];//质因数分解结果(无序的)int tot;//质因数的个数,数组下标从0开始ll Pollard_rho(ll x,ll c){ ll i=1,k=2; ll x0=rand()%x; ll y=x0; while(1){ i++; x0=(mult_mod(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 findfac(ll n){ if(Miller_Rabin(n)){//素数 factor[tot++]=n; return; } ll p=n; while(p>=n) p=Pollard_rho(p,rand()%(n-1)+1); findfac(p); findfac(n/p);}ll ans,fa[100];int nu;void dfs(int st,ll x,ll maxx){ if(st>nu){ if(x<=maxx&&x>ans) ans=x; return; } dfs(st+1,x,maxx); dfs(st+1,x*fa[st],maxx);}int main(){ //srand(time(NULL)); ll a,b; while(scanf("%lld%lld",&a,&b)==2){ if(a==b){ printf("%lld %lld\n",a,b); continue; } tot=nu=0; ll s=b/a; findfac(s); sort(factor,factor+tot); fa[0]=factor[0]; for(int i=1;i<tot;i++){//合并相同的素因子 if(factor[i]==factor[i-1]) fa[nu]*=factor[i]; else fa[++nu]=factor[i]; } ll x=(ll)sqrt(s*1.0); ans=1; dfs(0,1,x); printf("%lld %lld\n",ans*a,s/ans*a); } return 0;}
POJ 2429 long long 质因数分解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。