首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

poj 2429 (分解质因数)

2013-10-24 
poj2429(分解质因子)题意:给出两个数的最大公约数g,最小公倍数lcm,求出这两个数,有多种组合的,求出和最小

poj 2429 (分解质因子)

题意:给出两个数的最大公约数g,最小公倍数lcm,求出这两个数,有多种组合的,求出和最小的一组。

思路: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是较小的一个,控制它小于nif(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;}


热点排行