poj 2429 (分解质因子)

思路：g=gca(a,b);a*b=lcm*g;a/g*b/g=lcm/g;gcd(a/g,b/g)=1;就是把lcm/g分解成两个互质的因子。可以用Pollard rho分解子因子，然后再将相同的因子合并，再将因子分成两部分。

 

 

 

 

#include<iostream>  
#include<algorithm>  
#include<math.h>  
#include<stdio.h>    
#include<string.h>    
#include<time.h>    
#include<stdlib.h>    
typedef __int64 LL;   
LL a,b,sum;   
const int S=20;//随机算法判定次数，S越大，判错概率越小     
//***************Miller_Rabin 算法进行素数测试***************    
int cmp(void const *a,void const *b)  
{  
    if(*(LL *)a>*(LL *)b)  
        return 1;  
    else return -1;  
}  
LL mult_mod(LL a,LL x,LL n)//返回(a*x) mod n,a,x,n<2^63    
{    
    a%=n;x%=n;    
    LL ret=0;    
    while(x)    
    {    
        if(x&1){ret+=a;if(ret>=n)ret-=n;}    
        a<<=1;    
        if(a>=n)a-=n;    
        x>>=1;    
    }    
    return ret;    
}    
LL pow_mod(LL a,LL x,LL n)//返回a^x mod n    
{    
    if(x==1)return a%n;    
    int bit[70],k=0;    
    while(x)    
    {    
        bit[k++]=(x&1?1:0);    
        x>>=1;    
    }    
    LL ret=1;    
    for(--k;k>=0;k--)    
    {    
       ret=mult_mod(ret,ret,n);    
       if(bit[k])ret=mult_mod(ret,a,n);    
    }    
    return ret;    
}    
bool judge(LL a,LL n,LL x,LL t)//以a为基，n-1=x*2^t，检验n是不是合数    
{    
    LL ret=pow_mod(a,x,n),flag=ret;    
    for(LL i=1;i<=t;i++)    
    {    
        ret=mult_mod(ret,ret,n);    
        if(ret==1&&flag!=1&&flag!=n-1)return true;    
        flag=ret;    
    }    
    if(ret!=1)return true;    
    return false;    
}    
bool Miller_Rabin(LL n)    
{    
    if(n==2||n==5||n==7||n==11)return true;    
    if(n%2==0||n%5==0||n%7==0||n%11==0)return false;    
    LL x=n-1,t=0;    
    while((x&1)==0)x>>=1,t++;    
    bool flag=true;    
    if(t>=1&&(x&1)==1)    
    {    
        for(int i=1;i<=S;i++)    
        {    
            LL a=rand()%(n-1)+1;    
            if(judge(a,n,x,t)){flag=true;break;}    
            flag=false;    
        }    
    }    
    if(flag)return false;    
    else return true;    
}    
//*******pollard_rho 算法进行质因数分解*****************    
LL factor[100];//质因子    
int tot;//质因子个数    
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;    
}    
LL Pollard_rho(LL x,LL c)    
{    
    LL i=1,x0=rand()%x,y=x0,k=2;    
    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;    
        }    
    }    
}  
void find_factor(LL n) //递归进行质因数分解N    
{              
    if(Miller_Rabin(n))    
    {    
        factor[tot++] = n;return;            
    }    
    LL p=n;    
    while (p>=n) p=Pollard_rho(p,rand() % (n-1) +1);    
    find_factor(p);    
    find_factor(n/p);    
}  
void dfs(int k,LL ans,LL n)  
{  
    if(ans>n)return ;//ans是较小的一个，控制它小于n  
    if(k==tot)  
    {  
         if(ans+sum/ans<a+b)  
         {a=ans,b=sum/ans;}  
       return;  
    }  
    dfs(k+1,ans,n);  
    dfs(k+1,ans*factor[k],n);  
    return ;  
}  
int main()  
{  
    LL lcm,g,temp,flag;  
    int k,i;  
    while(scanf("%I64d%I64d",&g,&lcm)!=-1)  
    {  
        if(g==lcm)  
        {  
            printf("%I64d %I64d\n",g,lcm);  
            continue;  
        }  
       tot=0;sum=lcm/g;  
       find_factor(sum);  
       qsort(factor,tot,sizeof(factor[0]),cmp);  
       k=0;a=1;b=sum;  
       flag=temp=factor[0];  
       for(i=1;i<tot;i++)//合并相同的质因子得到互质的一些因子  
       {  
           if(factor[i]==temp)  
              flag*=temp;  
           else  
           {  
               factor[k++]=flag;  
               flag=temp=factor[i];  
           }  
       }  
       factor[k++]=flag;  
       tot=k;  
       dfs(0,1,(LL)sqrt(1.0*sum));//将得到的互质因子分成两部分  
       //if(a>b)std::swap(a,b);  
       printf("%I64d %I64d\n",a*g,b*g);  
    }  
    return 0;  
}  

 

补充：软件开发 , C++ ,