大数分解模板

发布时间：2020-12-14 02:25:42 所属栏目：大数据来源：网络整理

导读：1. Miller-Rabin 算法 (基于费马小定理/ Fermat 定理 ) 作用：通过概率的方式判断素数。有误判概率，通过多次判断可以使误判概率控制在很小范围。理论基础：如果n是一个奇素数，将n-1表示成2^s*r的形式(r是奇数)，a 是和n互素的任何整数，那么a^r≡1(mod

1.Miller-Rabin 算法(基于费马小定理/Fermat 定理)

作用：通过概率的方式判断素数。有误判概率，通过多次判断可以使误判概率控制在很小范围。

理论基础：如果n是一个奇素数，将n-1表示成2^s*r的形式(r是奇数)，a 是和n互素的任何整数，那么a^r≡1(mod n) 或者对某个j(0≤j ≤s -1， j∈Z) 等式 a^(2^j*r) ≡-1(mod n)成立。这个理论是通过一个事实经由Fermat定理推导而来： n是一个奇素数，则方程x2 ≡ 1 mod n只有±1两个解。

代码实现：

[cpp]? 
   view plain 
   copy 
   print 
   ? 
    
   
 #define?LL?__int64??
 const?LL?NUM=3;//判断次数，每次误判概率1/2.NUM次误判概率为2^(-num)??
 LL?check(LL?a,LL?n,LL?x,LL?t)//合数返回true??
 {??
 ????LL?ret=pow_mod(a,x,n);//a^x%n??
 ????LL?last=ret;??
 ????for(LL?i=1;i<=t;i++)??
 ????{??
 ????????ret=mult_mod(ret,ret,0); background-color:inherit">//ret^2%n，64位乘法，需要用二进制乘法，类似快速幂。??
 ????????if(ret==1?&&?last!=1?&&last!=n-1)return?true;??
 ????????last=ret;??
 ????}??
 ????if(ret!=1)return?true;??
 ????return?false;??
 }??
 bool?Miller_Rabin(LL?n)//Miller_Rabin算法,素数返回true??
 {??
 ????if(n<2)return?false;??
 ????if(n==2)return?true;??
 ????if((n&1)==0)return?false;??
 ????LL?x=n-1;??
 ????LL?t=0;??
 ????while((x&1)==0){x>>=1;t++;}??
 ????for(LL?i=0;i<NUM;i++)??
 ????{??
 ????????LL?a=rand()%(n-1)+1;//生成1~n-1的随机数??
 ????????if(check(a,n,t))??
 ????????????return?false;??
 ????}??
 ????return?true;??
 }??

2.?Pollard rhos算法：

作用：求解一个数的因子。

原理：设n为待分解的大整数，用某种方法生成a和b，计算p=gcd(a-b,n),直到p不为1或a,b出现循环时为止，若p=n，则说明n是一个素数，否则p为n的一个约数。

算法步骤：选取一个小的随机数x1，迭代生成x[i] = x[i-1]^2+c，一般取c=1，若序列出现循环则退出，计算p=gcd(x[i-1]-x[i],n)，若p=1则返回上一步继续迭代，否则跳出迭代过程。若p=n，则n为素数，否则p为n的一个约数，并递归分解p和n/p。

可以在θ（sqrt(p)）的期望时间内找到n的一个小因子p。但对于因子很少，因子值很大的大整数n，该方法依然不是很有效。

为了减少反复的次数，算法做了一些改进。该算法用数对(x0,x0)开始，并且用x(i+1)=f(xi)?，迭代计算(x1,x2),(x2,x4),(x3,x6)...(xi,x2i)。在每一次迭代中，我们都应用上述函数式运算(从第二步)第一次计算数对中的第一个元素，第二次计算数对中的第二个元素。

代码实现：

?

LL?Pollard_rho(LL?n,LL?c)//Pollard_rho算法，找出n的因子??

????LL?i=1,j,k=2,y,d,p;??
????x=rand()%n;??
????y=x;??
????while(true)??
????????i++;??
????????x=(mul_mod(x,n)+c)%n;??
????????if(y==x)return?n;??
????????if(y>x)p=y-x;??
????????else?p=x-y;??
????????d=gcd(p,n);??
????????if(d!=1&&d!=n)return?d;??
????????if(i==k)??
????????{??
????????????y=x;??
????????????k+=k;??
????????}??
}??

例子：hdu 3864

题目代码：http://www.voidcn.com/article/p-gmfoltuo-pz.html

3.三维求最大子长方体和（可推广到多维）

?

#include?<cstdio>??

#include?<cstring>??
#include?<cmath>??
#include?<cstdlib>??
#include?<iostream>??
#include?<algorithm>??
#include?<queue>??
#include?<map>??
#include?<set>??
#include?<vector>??
#include?<cctype>??
using?namespace?std;??
??
#define?LL?long?long??
void?expand(int?i,int?&b0,87); font-weight:bold; background-color:inherit">int?&b1,87); font-weight:bold; background-color:inherit">int?&b2)??
????b0=i&1;i>>=1;??
????b1=i&1;i>>=1;??
????b2=i&1;??
}??
int?sign(int?b0,87); font-weight:bold; background-color:inherit">int?b1,87); font-weight:bold; background-color:inherit">int?b2)??
????return?(b0+b1+b2)%2==1?1:-1;??
const?int?maxn=30;??
const?LL?INF=1LL<<60;??
LL?s[maxn][maxn][maxn];??
LL?sum(int?x1,87); font-weight:bold; background-color:inherit">int?x2,87); font-weight:bold; background-color:inherit">int?y1,87); font-weight:bold; background-color:inherit">int?y2,87); font-weight:bold; background-color:inherit">int?z1,87); font-weight:bold; background-color:inherit">int?z2)??
????int?dx=x2-x1+1,dy=y2-y1+1,dz=z2-z1+1;??
????LL?ss=0;??
????for(int?i=0;i<8;i++)??
???????? ????????expand(i,b0,b2);??
????????ss-=s[x2-b0*dx][y2-b1*dy][z2-b2*dz]*sign(b0,b2);??
????return?ss;??
int?main()??
int?T;??
????scanf("%d",&T);??
????while(T--)??
int?a,b,c,b2,z,x1,y1,x2,y2,i,k;??
????????scanf("%d%d%d",&a,&b,&c);??
????????memset(s,sizeof(s));??
????????for(x=1;x<=a;x++)??
????????????for(y=1;y<=b;y++)??
????????????????for(z=1;z<=c;z++)??
????????????????????scanf("%lld",&s[x][y][z]);??
????????????????????for(i=1;i<=7;i++)//容斥定理，奇加偶减??
????????????????????{??
????????????????????????expand(i,153); list-style:decimal-leading-zero outside; color:inherit; line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> ????????????????????????s[x][y][z]+=s[x-b0][y-b1][z-b2]*sign(b0,248)"> ????????????????????}??
????????LL?ans=-INF;??
????????for(x1=1;x1<=a;x1++)??
????????????for(x2=x1;x2<=a;x2++)??
????????????????for(y1=1;y1<=b;y1++)??
????????????????????for(y2=y1;y2<=b;y2++)??
????????????????????{??
????????????????????????LL?m=0;??
????????????????????????for(z=1;z<=c;z++)??
????????????????????????{??
????????????????????????????LL?ss=sum(x1,1,z);??
????????????????????????????ans=max(ans,ss-m);??
????????????????????????????m=min(m,ss);??
????????????????????????}??
????????printf("%lldn",ans);??
????????if(T!=0)printf("n");??
????return?0;??
/*?
一个a*b*c的长方体废料块，每个单位废料块有一个价值，求具有最大价值和的子立方体。?
*/

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!