基本数论算法

dalao博客，至少很好看。。

因为本人数论实在渣渣，但是考试确是得考的，只好尽早学，尽早掌握。

最大公因数

普通gcd

O(log(min(a,b)))

1 inline int gcd(int x,int y) 2
View Code

二进制优化gcd

O(log(min(a,b))) 没有%常数减小

1 inline int bsgcd(int x, int y) 2
View Code

素数判定

埃拉托色尼筛法

O(nloglogn)

不够优越，所以不学。

线性筛

模板题

O(n)

1 const int MAXN = 10000001; 2 3 bool notpri[MAXN]; 4 int n, m, cnt, prime[MAXN]; 5 6 inline void get_prime() 7 18 } 19 }
View Code

MillerRabin 大素数判定

cnblogs/vongang/archive/2012/03/15/2398626

模板题

O(log₃₂n)

费马小定理：对于素数p和任意整数a，有a^p≡ a(mod p)（同余）。反过来，满足a^p≡ a(mod p)，p也几乎一定是素数。

伪素数：如果p是一个正整数，如果存在和p互素的正整数a满足 a^p1≡ 1(mod p)，我们说p是基于a的伪素数。如果一个数是伪素数，那么它几乎肯定是素数。

MillerRabin测试：不断选取不超过p1的基a(s次)，计算是否每次都有a^p1≡ 1(mod p)，若每次都成立则p是素数，否则为合数。

还有一个定理，能提高Miller测试的效率：

二次探测定理：如果p是奇素数，则 x²≡ 1(mod p)的解为 x = 1 || x = p 1(mod p);

这个算法的正确率据说是3/4，所以多测几次。。

1 #include <cstdio> 2 #include <ctime> 3 #include <cstdlib> 4 #define LL long long 5 6 int n, ans; 7 const int S = 5; 8 9 //快速计算 a * b % p 10 inline LL mod_mul(LL a, LL b, LL p) 11 19 return ret; 20 } 21 22 //快速计算 a ^ b % p 23 inline LL mod_exp(LL a, LL b, LL p) 24 32 return ret; 33 } 34 35 inline bool miller_rabin(LL p) 36 57 if(x != 1) return 0; // 费马小定理 58 } 59 return 1; 60 } 61 62 int main() 73 printf("%d\n", ans); 74 } 75 return 0; 76 }
View Code

拓展欧几里得

能求出 ax + by = gcd(a,b) 的一组解，还能顺带求出 gcd

正常版

1 inline int exgcd(int a, int b, int &x, int &y) 3 int r = exgcd(b, a % b, x, y); 4 int t = x, x = y, y = t a / b * y; 5 return r; 6 }
View Code

极简版

1 inline int exgcd(int a, int b, int &x, int &y) 2 4 int r = exgcd(b, a % b, y, x); 5 y = a / b * x; 6 return r; 7 }
View Code

证明——其实就是推一下式子，

ax+by=gcd(a,b) ①

bx'+(a%b)y'=gcd(b,a%b) ②

已知x'和y'求x和y

∵gcd(a,b)=gcd(b,a%b)

∴ax+by=bx'+(a%b)y'

ax+by=bx'+(aa/b*b)y'

ax+by=bx'+ay'a/b*by'

ax+by=ay'+b(x'a/b*y')

∴x=y'，y=x'a/b*y'

证毕，但要注意除法都是下取整的

快速幂

递归版

1 #define LL long long 2 inline LL pow(LL a, LL b, LL p) 3
View Code

非递归版

1 #define LL long long 2 inline LL pow(LL a, LL b, LL p) 3 11 return ans; 12 }
View Code

膜意义下的逆元

若 a*x≡1(mod b)，且a和b互质，则称x为a的逆元，记作a¹

逆元的求解方法：

1.快速幂

如果p是质数，那么 a 的逆元为 a^p2，好像是通过什么费马小定理证明的，记住就行

2.扩展欧几里得

定义式可以转化为a*x+b*y==1，所以自然可以利用扩展欧几里得求啦！

3.线性递推

首先1¹≡1(mod p)，

假设p=k*i+r，r<i，1<i<p，那么k*i+r≡0(mod p)

等式两边同时乘上i¹，r¹，式子就变成k*r¹+i¹≡0(mod p)

i¹≡k*r¹

i¹≡(p/i)*(p mod i)¹

这样便可以线性递推求解

#include <cstdio> #define N 3000001 int n, p; int inv[N] = ; int main() return 0; }

卢卡斯定理——用于解决组合数的取膜问题

卢卡斯定理

C(n,m)%p=C(n%p,m%p)*C(n/p,m/p)%p

至于证明。。算了吧，背过得了

因为p不大

所以C(n%p,m%p)可直接求出，

但是如果n%p<m%p时返回0

C(n/p,m/p)可继续递归求解

当m==0时返回1

#include <cstdio> #define N 200001 #define LL long long int T; int F[N], inv[N]; inline int C(int n, int m, int p) inline int Lucas(int n, int m, int p) int main() return 0; }

　　

上一篇：[luoguP1119] 灾后重建（Floyd）

下一篇：[luoguP2216] [HAOI2007]理想的正方形（二维单调队列）

---

模板 数论 素数筛 扩展欧几里得 逆元 卢卡斯定理