[原创]POJ 2429 GCD&LCM Inverse [pollard_rho]【数论】

/*******************Miller_Rabin素数测试&&Pollard_rho整数分解**************************/ 
# include <cstdio>
# include <cmath>
# include <ctime>
# include <cstdlib>
# include <cstring>
# include <string>
# include <algorithm>
# include <iostream>
# define Times 11
# define MAX ((long long)1<<61) 
# define N 501
# define C 201
# define LL long long
using namespace std;


int ct,cnt;
LL mini,jl[N],factor[N],num[N];
LL mina,minb,ans,n,m;

LL gcd(LL a,LL b){
    return b==0?a:gcd(b,a%b);
}

LL random(LL n){
    return (LL)((double)rand()/RAND_MAX*n+0.5);
}

LL multi(LL m,LL n,LL k){
    LL b=0;
    while(n){
        if(n&1) b=(b+m)%k;
        n>>=1;
        m=(m<<1)%k;
    }
    return b;
}

LL quick_mod(LL m,LL n,LL k){
    LL b=1;
    m%=k; 
    while(n){
        if(n&1) b=multi(b,m,k);
        n/=2;
        m=multi(m,m,k);
    }
    return b;
}

bool Witness(LL a,LL n){
    LL m=n-1;
    int j=0;
    while(!(m&1)){
        j++;
        m>>=1;
    }
    LL x=quick_mod(a,m,n);
    if(x==1||x==n-1) return false;
    while(j--){
        x=x*x%n;
        if(x==n-1) return false;
    }
    return true;
}

bool Miller_Rabin(LL n){
    if(n<2) return false;
    if(n==2) return true;
    if(!(n&1)) return false;
    for(int i=1;i<=Times;i++){
        LL a=random(n-2)+1;
        if(Witness(a,n)) return false;
    }
    return true;
}

LL Pollard_rho(LL n,int c){
    LL x,y,d,i=1,k=2;
    x=random(n-1)+1;
    y=x;
    while(1){
        i++;
        x=(multi(x,x,n)+c)%n;
        d=gcd(y-x,n);
        if(1<d&&d<n) return d;
        if(y==x) return n;
        if(i==k){
            y=x;
            k<<=1;
        }
    }
}

void find(LL n,int k){
    if(n==1) return ;
    if(Miller_Rabin(n)){
        jl[++ct]=n;
        return ;
    }
    LL p=n;
    while(p>=n) p=Pollard_rho(p,k--);
    find(p,k);
    find(n/p,k);
}

void dfs(LL c,LL value){
    LL s=1,a,b;
    if(c==cnt+1){
        a=value;
        b=ans/a;
        if(gcd(a,b)==1){
            a*=n;
            b*=n;
            if(a+b<mini){
                mini=a+b;
                mina=a; minb=b;
            }
        }
        return ;
    }
    for(LL i=0;i<=num[c];i++){
        if(s*value>mini) return ;
        dfs(c+1,s*value);
        s*=factor[c];
    }
}

int main(){
    
//    freopen("data.in","r",stdin);
//    freopen("data.out","w",stdout);
    
//    srand(time(NULL));  
    while(scanf("%lld%lld",&n,&m)!=EOF){
        if(n==m) {printf("%lld %lld\n",n,m); continue;}
        mini=MAX;
        ct=cnt=0;
        ans=m/n; 
        find(ans,C);
        sort(jl+1,jl+ct+1);
        memset(factor,0,sizeof(factor));
        memset(num,0,sizeof(num));
        num[0]=1;
        factor[0]=jl[1];
        for(int i=2;i<=ct;i++){
            if(jl[i]!=jl[i-1]) factor[++cnt]=jl[i];
            num[cnt]++;
        }
        dfs(0,1);
        if(mina>minb) swap(mina,minb);
        printf("%lld %lld\n",mina,minb);
    }
    return 0;
}