260
POJ2429 Pollard rho因子分解
題意給出最大公約數和最小公倍數，讓求出滿足這個條件的兩個數並且該兩個數的和最小。並按照從小到大的順序輸出。因子分解用的是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;
}
最後更新：2017-04-04 07:03:54