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;
}

  
目录
相关文章
|
机器学习/深度学习 算法
算法提高:组合数学| 卡特兰数的实现
卡特兰数列是组合数学中在各种计数问题中常出现的数列,其前几项为1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012…… 卡特兰数首先是由欧拉在计算对凸n边形的不同的对角三角形剖分的个数问题时得到的,即在一个凸n边形中,通过不相交于n边形内部的对角线,把n边形拆分成若干三角形,不同的拆分数用Hn表示,Hn即卡特兰数。
140 0
算法提高:组合数学| 卡特兰数的实现
|
网络架构
POJ-1005,I Think I Need a Houseboat(数学题)
POJ-1005,I Think I Need a Houseboat(数学题)
|
算法
POJ 3154 Graveyard【多解,数论,贪心】
Graveyard Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 1707   Accepted: 860   Special Judge Description Prog...
1248 0
数论 + 公式 - HDU 4335 What is N?
What is N?  Problem's Link:  http://acm.hdu.edu.cn/showproblem.php?pid=4335   Mean:  给你三个数b、P、M,让你求有多少个n满足下式。
860 0
|
算法
【算法导论】幻方算法
        说起幻方,大家应该在小学时候就已经接触过了,最简单的就是九宫格,射雕英雄传中的那段至今还记得:戴九履一,左三右七,二四为肩,六八为足。
1150 0
|
算法 数据安全/隐私保护 BI
Miller-Rabin素性测试(POJ3641)
一.概念引入         在以往判断一个数n是不是素数时,我们都是采用i从2到sqrt(n)能否整除n.如果能整除,则n是合数;否则是素数.但是该算法的时间复杂度为O(sqrt(n)),当n较大时,时间性能很差,特别是在网络安全和密码学上一般都是需要很大的素数.而从目前来看,确定性算法判断素数的性能都不好,所以可以用MC(蒙特卡洛)概率算法来解决,其中Miller Rabin算法就是其中的很经典的解决方法.下面首先介绍下相关的数学理论。
1024 0