POJ2429 - GCD & LCM Inverse(Miller–Rabin+Pollard's rho)
2024-10-12 14:30:30
题目大意
给定两个数a,b的GCD和LCM,要求你求出a+b最小的a,b
题解
GCD(a,b)=G
GCD(a/G,b/G)=1
LCM(a/G,b/G)=a/G*b/G=a*b/G^2=L/G
这样的话我们只要对L/G进行质因数分解,找出最接近√(L/G)的因子p,最终结果就是a=p*G,b=L/p,对(L/G)就是套用Miller–Rabin和Pollard's rho了,刚开始Pollard's rho用的函数也是
f(x)=x^2+1,然后死循环了。。。。改成f(x)=x^2+c(c<=181)就OK了
代码:
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<algorithm>
#define MAXN 100000
using namespace std;
typedef unsigned long long LL;
LL fac[MAXN],cnt,G,L,m,p;
LL min(LL a,LL b)
{
return a<b?a:b;
}
LL gcd(LL a,LL b)
{
return b==0?a:gcd(b,a%b);
}
LL mult_mod(LL a,LL b,LL mod)
{
LL ans=0;
while(b)
{
if(b&1)
ans=(ans+a)%mod;
a=(a<<1)%mod;
b>>=1;
}
return ans;
}
LL pow_mod(LL a,LL b,LL mod)
{
LL d=1;
a%=mod;
while(b)
{
if(b&1)
d=mult_mod(d,a,mod);
a=mult_mod(a,a,mod);
b>>=1;
}
return d%mod;
}
bool witness(LL a,LL n)
{
LL u=n-1,t=0;
while((u&1)==0)
{
u>>=1;
t++;
}
LL x,x0=pow_mod(a,u,n);
for(LL i=1; i<=t; i++)
{
x=mult_mod(x0,x0,n);
if(x==1&&x0!=1&&x0!=(n-1))
return true;
x0=x;
}
if(x!=1)
return true;
return false;
}
bool miller_rabin(LL n)
{
if(n==2) return true;
if(n<2||!(n&1)) return false;
for(int j=1; j<=8; j++)
{
LL a=rand()%(n-1)+1;
if(witness(a,n))
return false;
}
return true;
}
LL pollard_rho(LL n,LL c)
{
LL i=1,k=2,d,x=2,y=2;
while(true)
{
i++;
x=(mult_mod(x,x,n)+c)%n;
d=gcd(y-x,n);
if(d!=1&&d!=n)
return d;
if(x==y) return n;
if(i==k)
{
y=x;
k<<=1;
}
}
}
void find_fac(LL n,LL c)
{
if(miller_rabin(n)||n<=1)
{
fac[cnt++]=n;
return;
}
LL p=pollard_rho(n,c);
while(p>=n) p=pollard_rho(p,c--);
find_fac(p,c);
find_fac(n/p,c);
}
void dfs( LL step,LL num)
{
if(step==cnt||num>p)
{
if(num<=p&&num>m)
m=num;
return;
}
dfs(step+1,num*fac[step]);
dfs(step+1,num);
}
int main()
{
srand(time(NULL));
while(scanf("%I64u%I64u",&G,&L)!=EOF)
{
cnt=0;
find_fac(L/G,181);
sort(fac,fac+cnt);
LL i=0,t=0;
while(i<cnt)
{
LL ans=1,j=i;
while(j<cnt&&fac[i]==fac[j])
{
ans*=fac[i];
j++;
}
fac[t++]=ans;
i=j;
}
cnt=t,m=1,p=sqrt(0.0+(L/G));
dfs(0,1);
printf("%I64u %I64u\n",m*G,L/m);
}
return 0;
}
最新文章
- 关于二叉排序树 BST
- 【洛谷P1351】联合权值
- python zip enumerate函数
- Linux静态库和共享库
- tp集成支付宝担保支付
- Python 基础教程中的问题及解决方案(1)
- mysql日志文件相关的配置【2】
- 用java代码发送http请求
- json格式的中文输出显示
- 树莓派做下载服务器 aria2 篇
- 彻底搞懂CSS文本、空白换行问题
- match和search的区别
- 解决 在Android开发上使用KSOAP2上传大图片到服务器经常报错的问题
- 在属性property做一些简单的验证
- 【LOJ#6283】数列分块7
- angularjs入门(二)
- PHP-FPM高负载的解决办法
- Node.js事件驱动模型
- Nginx 安装与启动
- LWIP内存管理
热门文章
- puppet 部署 horizon server 所需的参数和部署逻辑
- IOS中如何判断APP是否安装后首次运行或升级后首次运行
- Tomcat安装与配置图文教程
- Core管道中的处理流程3
- CSS使块半透明方法,兼容IE6
- HDU 2370 Convert Kilometers to Miles
- loadrunner 怎么能得到返回的http状态?
- Java异常处理之throws抛出异常
- QT带OpenGL与不带的区别,QT5是一个伟大的框架,短时期内根本不会有替代者
- Inventory >; INV.MTL_MATERIAL_TRANSACTIONS Show Error Msg: ORA-20100: File lxxx.tmp creation for FND_FILE failed.