现在的位置: 首页 > 综合 > 正文

POJ2429 GCD&LCM Inverse(整数分解，由GCD+LCM求a,b) POJ2429 GCD&LCM Inverse(整数分解，由GCD+LCM求a,b)

2017年11月04日 ⁄ 综合 ⁄ 共 3512字 ⁄ 字号 小 中 大 ⁄ 评论关闭
 

POJ2429 GCD&LCM Inverse(整数分解，由GCD+LCM求a,b)

分类： 数论2013-02-12
22:00 180人阅读 评论(1) 收藏 举报

题目：GCD & LCM Inverse

 

题意：给你两个数G和L分别是a,b的最大公约数和最小公倍数，求a,b。（有多组a,b的情况下取a+b最小的）

 

分析：由于 G和L分别是a，b的最大公约数和最小公倍数，那么G一定整除L，否则就没有解了。

进一步可以知道L/G的素因子分解式中，同一项不会同时出现在a，b中，因为相同的在G中已经除掉了.

 

那么有：，所以我们现在只需要枚举L/G的约数，枚举的一个x在a中，那么另一个(L/G)/x就是在b中，但是我们知道

 

,,所以思路就是对L/G先分解，因为这个数很大，所以就用Pollard-rho分解法吧，分解之后，利用

 

dfs找因子，然后每找到一个就判断一次来记录a+b最小的，然后就分析完毕。

 

 

[cpp] view
plaincopy

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <string.h>  
  4. #include <algorithm>  
  5. #include <iostream>  
  6.   
  7. using namespace std;  
  8. #define LL unsigned long long  
  9.   
  10. const int Times=10;  
  11. const LL INF=(LL)1<<61;  
  12. const int N=550;  
  13.   
  14. LL n,m,ct,cnt,mini,mina,minb,ans;  
  15. LL fac[N],num[N];  
  16.   
  17. LL gcd(LL a,LL b)  
  18. {  
  19.     return b? gcd(b,a%b):a;  
  20. }  
  21.   
  22. LL multi(LL a,LL b,LL m)  
  23. {  
  24.      LL ans=0;  
  25.      while(b)  
  26.      {  
  27.          if(b&1)  
  28.          {  
  29.              ans=(ans+a)%m;  
  30.              b--;  
  31.          }  
  32.          b>>=1;  
  33.          a=(a+a)%m;  
  34.      }  
  35.      return ans;  
  36. }  
  37.   
  38. LL quick_mod(LL a,LL b,LL m)  
  39. {  
  40.      LL ans=1;  
  41.      a%=m;  
  42.      while(b)  
  43.      {  
  44.          if(b&1)  
  45.          {  
  46.              ans=multi(ans,a,m);  
  47.              b--;  
  48.          }  
  49.          b>>=1;  
  50.          a=multi(a,a,m);  
  51.      }  
  52.      return ans;  
  53. }  
  54.   
  55. bool Miller_Rabin(LL n)  
  56. {  
  57.     if(n==2) return true;  
  58.     if(n<2||!(n&1)) return false;  
  59.     LL a,m=n-1,x,y;  
  60.     int k=0;  
  61.     while((m&1)==0)  
  62.     {  
  63.         k++;  
  64.         m>>=1;  
  65.     }  
  66.     for(int i=0;i<Times;i++)  
  67.     {  
  68.         a=rand()%(n-1)+1;  
  69.         x=quick_mod(a,m,n);  
  70.         for(int j=0;j<k;j++)  
  71.         {  
  72.             y=multi(x,x,n);  
  73.             if(y==1&&x!=1&&x!=n-1) return false;  
  74.             x=y;  
  75.         }  
  76.         if(y!=1) return false;  
  77.     }  
  78.     return true;  
  79. }  
  80.   
  81. LL Pollard_rho(LL n,LL c)  
  82. {  
  83.      LL x,y,d,i=1,k=2;  
  84.      y=x=rand()%(n-1)+1;  
  85.      while(true)  
  86.      {  
  87.          i++;  
  88.          x=(multi(x,x,n)+c)%n;  
  89.          d=gcd((y-x+n)%n,n);  
  90.          if(1<d&&d<n) return d;  
  91.          if(y==x) return n;  
  92.          if(i==k)  
  93.          {  
  94.              y=x;  
  95.              k<<=1;  
  96.          }  
  97.      }  
  98. }  
  99.   
  100. void find(LL n,int c)  
  101. {  
  102.      if(n==1) return;  
  103.      if(Miller_Rabin(n))  
  104.      {  
  105.          fac[ct++]=n;  
  106.          return ;  
  107.      }  
  108.      LL p=n;  
  109.      LL k=c;  
  110.      while(p>=n) p=Pollard_rho(p,c--);  
  111.      find(p,k);  
  112.      find(n/p,k);  
  113. }  
  114.   
  115. void dfs(LL c,LL value)  
  116. {  
  117.      LL s=1,a,b;  
  118.      if(c==cnt)  
  119.      {  
  120.          a=value;  
  121.          b=ans/a;  
  122.          if(gcd(a,b)==1)  
  123.          {  
  124.              a*=n;  
  125.              b*=n;  
  126.              if(a+b<mini)  
  127.              {  
  128.                  mini=a+b;  
  129.                  mina=a;  
  130.                  minb=b;  
  131.              }  
  132.          }  
  133.          return ;  
  134.      }  
  135.      for(LL i=0;i<=num[c];i++)  
  136.      {  
  137.          if(s*value>mini) return;  
  138.          dfs(c+1,s*value);  
  139.          s*=fac[c];  
  140.      }  
  141. }  
  142.   
  143. int main()  
  144. {  
  145.     while(~scanf("%llu%llu",&n,&m))  
  146.     {  
  147.          if(n==m)  
  148.          {  
  149.              printf("%llu %llu\n",n,m);  
  150.              continue;  
  151.          }  
  152.          mini=INF;  
  153.          ct=cnt=0;  
  154.          ans=m/n;  
  155.          find(ans,120);  
  156.          sort(fac,fac+ct);  
  157.          num[0]=1;  
  158.          int k=1;  
  159.          for(LL i=1;i<ct;i++)  
  160.          {  
  161.              if(fac[i]==fac[i-1])  
  162.                  ++num[k-1];  
  163.              else  
  164.              {  
  165.                  num[k]=1;  
  166.                  fac[k++]=fac[i];  
  167.              }  
  168.          }  
  169.          cnt=k;  
  170.          dfs(0,1);  
  171.          if(mina>minb) swap(mina,minb);  
  172.          printf("%llu %llu\n",mina,minb);  
  173.     }  
  174.     return 0;  
  175. }  
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞