总结一下常见的算法和定理,不作证明与解释
1.素数判定-Miller Rabbin算法.
要判定n是否为质数,随机一个数x,看是否为1,如果是,若可以将其开方那么就开,根据二次探测定理,x^2=1(mod p)当且仅当x=1或p-1,那么就可以检测,代码如下.
bool MR(int n){ if(n<3) return n==2; int a=n-1,b=0; while(a%2==0) a/=2,b++; for(int i=1,j;i<=10;i++){ int x=ksm(rand()%(n-2)+2,a,n); if(x==n-1 || x==1) continue; for(j=0;j<b;j++){ x=1ll*x*x%n; if(x==n-1) break; } if(j==b) return false; } return true; }2.exgcd
可以在O(log n)的时间内求出的整数解(x,y)
具体方法看代码.
int exgcd(int a,int b,int&x,int&y){ if(b==0){ x=1;y=0; return a; } int d=exgcd(b,a%b,y,x); y=y-a/b*x; return d; }3.欧拉函数
表示1-n中与n互质的数的个数.
可以证明:
求欧拉函数值可以暴力分解质因数,时间复杂度
或者可以使用Pollard's Rho算法优化到约
4.Pollard's Rho算法
这是一种用来快速分解质因数的算法,时间复杂度大概是
实际上时间复杂度很小,后面那个log几乎可以省去,算法流程大概就是随机一个c,定义一个函数,显然一个数的值只与上一个数的值有关,那么必成一个环/一段数+一个环,我们总共要尝试个数,才能把n的质因子给试出来,可以发现,环上距离差为k的数值差与n的gcd是相同的,所以时间复杂度就被降为了,我们只需要枚举两个指针,一个指针一次跳一步,即,另一个指针一次跳两步,即,这样当为1时,那么可以继续操作,若为n,那么说明这种循环分解不出更小的因数,否则就分解出了更小的因数,返回即可.但是考虑到这样的时间复杂度瓶颈会在gcd上,大大减慢了程序的速度,所以我们可以考虑倍增累计乘法,也就是将算法中距离个数乘起来,再与n做gcd,但是这样出来的gcd可能会偏大,为1时,这个数与n的gcd都为1,为n时,我们说不清楚是否在其中产生了答案,xuyixuan的做法就是暴力判断其中是否产生了新的答案,如果没有产生,这种函数必不可行,直接返回,否则就产生了新的答案,其他人的做法就是不用管,直接返回,换新的函数来求解.笔者用的是后者,并且将倍增上界设为127
ll pr(ll mod){ if(mod%2==0) return 2; ll s=0,t=0,c=1ll*rand()*rand()%(mod-1)+1; for(int i=1;;i<<=1,s=t){ ll tot=1; for(int j=1;j<=i;j++){ mul(t,t,mod); t+=c;t>=mod?t-=mod:0; mul(tot,abs(t-s),mod); if(j%127==0){ ll d=gcd(tot,mod); if(d!=1) return d; } } ll d=gcd(tot,mod); if(d!=1) return d; } } void fac(ll n){ if(mr(n)){ mx=max(mx,n); return ; } ll op=pr(n); while(op==1 || op==n) op=pr(n); fac(op);fac(n/op); }5.费马小定理&欧拉定理&扩展欧拉定理
费马小定理:若,那么就有
欧拉定理:若,那么就有
这两者都可以用乘法群和互质的性质来证明
扩展欧拉定理:
只需要证明最后一条,我们设p为a的任意质因数,那么设,那么就有
所以从r开始,就进入了一个的数循环.而且因为
.
从而可以得到
对于一个来说,同样可以类似证明,然后同余式支持乘法合并,左右乘起来就可以得到扩展欧拉定理.
6.类欧几里得算法
具体可以参考我这一篇,考场上可能不怎么能推出来,就算推得出来肯定很耗时间,所以还是背一背公式把.
7.中国剩余定理
具体可以参考我这一篇
8.原根相关与二次剩余
具体可以参考我这一篇
9.BSGS
具体可以参考我这一篇
10.Lucas定理
具体可以参考我这一篇,证明和一些数学相关的东西都在这一篇里
11.莫比乌斯反演
这个常考,也比较简单,但是涉及到的基础证明可能比较复杂,可以直接看我这一篇
12.杜教筛和min_25筛
在我的印象当中,min_25筛是严格优于杜教筛的,但是杜教筛相对于min_25筛来说很好想.
基础知识就学完了,要做题才能理解数论的奥妙.欢迎来到51nod
