河南理工大学第三次公开课
素数
什么是质数
质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。
基本思想找质数
1 | #include <bits/stdc++.h> // 万能头文件 |
时间小优化
1 | #include <bits/stdc++.h> |
但是上面两种方法有个很大的弊病,就是不能一次筛出很多素数,加入我们要筛出(1~1e5)之间的所有素数,上面两种方法就很慢了,时间复杂度是O(n^2)
普通筛——埃拉托斯特尼(Eratosthenes)筛法
1 | #include <bits/stdc++.h> |
大神筛法–欧拉筛
1 | bool IsPrime[1000010]; |
扩展
快速幂
求 a^b 朴素算法
1 | #include <bits/stdc++.h> |
当b为1e9的时候在1s的时间内程序是远远计算不出来的,因此我们需要改进算法
例如5^10 , 10 的二进制表示为 1010
5^10 = 5^(2^2+2^8)
1 | #include <bits/stdc++.h> |
时间复杂度O(n*lgn)
模
费马小定理
费马小定理(Fermat’s little theorem)是数论中的一个重要定理,在1636年提出。如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1(mod p)。
逆元
当求解公式:(a/b)%m 时,因b可能会过大,会出现爆精度的情况,所以需变除法为乘法:
设c是b的逆元,则有bc≡1(mod m);
则(a/b)%m = (a/b)1%m = (a/b)bc%m = ac(mod m);
即a/b的模等于ab的逆元的模;
费马小定理+快速幂求逆元
1 | #include <bits/stdc++.h> |
利用逆元求组合数
1 | #include <cstdio> |
扩展gcd求组合数
1 | #include <cstdio> |
扩展