初等数论学习笔记I：同余相关。CHANGELOG2022.7.13：重构文章，更新PR模板代码。2023.1.23：对文章进行修补。1.Miller-RabinMiller-Rabin素性测试是一种具有随机性的素数判定方法。它有一定概率将合数判定为素数，但不会将素数判定为合数。素数判定的基本思路为根据所有质数但很少合数具有的性质，检查被判定的数是否具有这些性质。若不具有，则该数是合数，否则该数大概率是质数。1.1费马素性检验当\(p\)是素数时，对于任意\(a\perpp\)均有\(a^{p-1}\equiv1\pmodp\)。相反，当\(a^{p-1}\equiv1\pmodp\)时，是否有
初等数论学习笔记I：同余相关。CHANGELOG2022.7.13：重构文章，更新PR模板代码。2023.1.23：对文章进行修补。1.Miller-RabinMiller-Rabin素性测试是一种具有随机性的素数判定方法。它有一定概率将合数判定为素数，但不会将素数判定为合数。素数判定的基本思路为根据所有质数但很少合数具有的性质，检查被判定的数是否具有这些性质。若不具有，则该数是合数，否则该数大概率是质数。1.1费马素性检验当\(p\)是素数时，对于任意\(a\perpp\)均有\(a^{p-1}\equiv1\pmodp\)。相反，当\(a^{p-1}\equiv1\pmodp\)时，是否有
组合数学排列与组合抽屉原理（鸽巢原理）把n+1个苹果放入n个抽屉里，则至少有一个抽屉放了两个或两个以上的苹果；从另一个角度来说，把n-1个苹果放入n个抽屉，则至少有一个抽屉是空的。如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素。假如有n+1个元素放入n个集合，其中必定有一个集合里至少有两个元素；把n-1个元素放入n个集合，则至少有一个集合是空的。通常来说，在问题中，较多的一方就是苹果，较少的一方就是抽屉。最差原则即考虑所有可能的情况中，最不利于某件事情发生的情况。容斥原理基本计数原理分类加法计数原理做一件事，完成它有\(n\)类方法，第一类有\(m_{1}\)种，第二类有\(m_{2}
组合数学排列与组合抽屉原理（鸽巢原理）把n+1个苹果放入n个抽屉里，则至少有一个抽屉放了两个或两个以上的苹果；从另一个角度来说，把n-1个苹果放入n个抽屉，则至少有一个抽屉是空的。如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素。假如有n+1个元素放入n个集合，其中必定有一个集合里至少有两个元素；把n-1个元素放入n个集合，则至少有一个集合是空的。通常来说，在问题中，较多的一方就是苹果，较少的一方就是抽屉。最差原则即考虑所有可能的情况中，最不利于某件事情发生的情况。容斥原理基本计数原理分类加法计数原理做一件事，完成它有\(n\)类方法，第一类有\(m_{1}\)种，第二类有\(m_{2}
·质数素数定理：设\(x\geq1\),以\(\pi(x)\)表示不超过\(x\)的素数的个数。当\(x\rightarrow\infty\)时，\(\pi(x)\to\dfrac{x}{\ln(x)}\)质数筛法1.埃式筛：从小到大一次枚举质数，将\(\left[1,n\right]\)内的所有倍数都标记为合数，未被标记的则为质数。2.线性筛：保证对任一合数，只会被其最小质因数标记。对于每一个数\(i\)，从小到大枚举当前质数集\(p\)，\(p_j\leqi\)，标记合数\(i\timesp_j\)，若\(p_j|i\)说明\(i=p_j\timesu\)；对于\(p_j，\(i\time
·质数素数定理：设\(x\geq1\),以\(\pi(x)\)表示不超过\(x\)的素数的个数。当\(x\rightarrow\infty\)时，\(\pi(x)\to\dfrac{x}{\ln(x)}\)质数筛法1.埃式筛：从小到大一次枚举质数，将\(\left[1,n\right]\)内的所有倍数都标记为合数，未被标记的则为质数。2.线性筛：保证对任一合数，只会被其最小质因数标记。对于每一个数\(i\)，从小到大枚举当前质数集\(p\)，\(p_j\leqi\)，标记合数\(i\timesp_j\)，若\(p_j|i\)说明\(i=p_j\timesu\)；对于\(p_j，\(i\time
参考资料：1.https://www.bilibili.com/video/BV1x3411s7Sy/?spm_id_from=333.788&vd_source=e66dd25b0246f28e772d75f11c80f03c2.余红兵：《数学奥林匹克小丛书（第二版）高中卷10————数论》素数 素数的定义：除了1和它本身以外不再有其他因数的自然数。亦即，除了1和n以外，并无其他正整数整除n的正整数.1既不是素数，也不是合数。n为合数，则有n=ab;n>a>1,n>b>1.我们可以视正整数为3类数。1为单独一类数，其二素数，其三合数.素数（primenumber）的表示常用字母p。引理
参考资料：1.https://www.bilibili.com/video/BV1x3411s7Sy/?spm_id_from=333.788&vd_source=e66dd25b0246f28e772d75f11c80f03c2.余红兵：《数学奥林匹克小丛书（第二版）高中卷10————数论》素数 素数的定义：除了1和它本身以外不再有其他因数的自然数。亦即，除了1和n以外，并无其他正整数整除n的正整数.1既不是素数，也不是合数。n为合数，则有n=ab;n>a>1,n>b>1.我们可以视正整数为3类数。1为单独一类数，其二素数，其三合数.素数（primenumber）的表示常用字母p。引理
参考资料：1.https://www.bilibili.com/video/BV1x3411s7Sy/?spm_id_from=333.788&vd_source=e66dd25b0246f28e772d75f11c80f03c2.http://t.csdn.cn/diQ272.余红兵：《数学奥林匹克小丛书（第二版）高中卷10————数论》最大公约数 设a,b∈Z，如果d∈Z且d|a,d|b，则称d是a和b的公因子（公约数）。若d>=0,且a和b的所有公因子都整除d，则称d是a和b的最大公约数，记作gcd(a,b).之前CSDN上我也写过一篇gcd筛：https://blog.csdn.
参考资料：1.https://www.bilibili.com/video/BV1x3411s7Sy/?spm_id_from=333.788&vd_source=e66dd25b0246f28e772d75f11c80f03c2.http://t.csdn.cn/diQ272.余红兵：《数学奥林匹克小丛书（第二版）高中卷10————数论》最大公约数 设a,b∈Z，如果d∈Z且d|a,d|b，则称d是a和b的公因子（公约数）。若d>=0,且a和b的所有公因子都整除d，则称d是a和b的最大公约数，记作gcd(a,b).之前CSDN上我也写过一篇gcd筛：https://blog.csdn.
