老久以前的了，以前忘放上面了（差点丢了/jk） 目录 欧拉筛素数 同余 辗转相除法证明 exgcd 中国剩余定理 扩展CRT 乘法逆元 欧拉函数 康托展开 卢卡斯定理/Lucas 定理 欧拉筛素数 (O(n))筛法 for(int i = 2; i <= n; i++) { if(vis[i] == 0) pre[tot++] =...
注意: 如果没有特殊说明, 以下讨论的都是针对n为素数时的时间复杂度 1. 根据概念判断: 如果一个正整数只有两个因子, 1和p，则称p为素数. 代码: bool isPrime(int n) { if(n < 2) return false; for(int i = 2; i < n; ++i) if...
数论部分第一节：素数与素性测试 一个数是素数（也叫质数），当且仅当它的约数只有两个——1和它本身。规定这两个约数不能相同，因此1不是素数。对素数的研究属于数论范畴，你可以看到许多数学家没事就想出一些符合某种性质的素数并称它为某某某素数。整个数论几乎就围绕着整除和素数之类的词转过去转过来。对于写代码的人来说，素数比想像中的更重要，Google一下Bi...