关于素数
朴素素数判定
埃氏素数筛法
线性欧拉筛法
Miller-Rabin素性测试
关于最大公因数
递归求gcd
扩展欧几里德算法(exgcd)
关于组合数
杨辉三角求组合数
逆元打表求组合数
Lucas定理
分块打表求组合数
零散的知识点
唯一分解定理
同余定理
加减乘同余
逆元同余
欧拉函数/欧拉降幂
[算法]数论基础小结
数论是纯粹数学的分支之一,主要研究整数的性质.被誉为"最纯"的数学领域.
总结了一些在寒假集训的时候学到的数论知识,不按难度排序.
素数,指除了1和它本身没有其他因数的正整数.
即从定义出发,遍历从2到根号n所有数.如果存在一个数字是他的因数,则这个数不是素数.
实现代码如下:
bool c