2nd 2022/5/3-2022/5/4 简单数论学习

标签：埃氏 数论 质数 相除 2nd 算法 2022 欧拉

Day-1/2:2022/5/3

·1 最大公约数

1. 枚举。。。训算法

2. 质因数分解。。。是个办法，但大材小用，浪费了算法得来的其他数据，时间较慢

3. 欧几里得算法，辗转相除，巧妙消元，时间$O(\log n)$

4. 二进制算法？？？

·2 扩展欧几里得

少有此类，但很需要学习

其实是辗转相除换了个方式出现，同样是通过不断缩小元直至特殊解，然后一路推回去

·3 容斥原理

经常接触，就是减去重复部分，较Easy

·4 欧拉函数

定义即对于一个正整数来说，比它小且和它互质的数的个数，能用欧拉筛法$O(n)$

解

·5 筛法：埃氏/欧拉

埃氏简单，即用质数筛去后面肯定不是质数的数

欧拉即埃氏减去重复

（细节：所有数都筛，只用晒质数倍，且只当自己是它的最小质因数才筛它）

·6即·7 欧拉定理

 

·8 威尔逊定理

给出了判断质数的充分必要条件

 

·9 逆元

可转换为exgcd

即

给出a、b，求$ax\equiv 1(mod\space b)$

可转换为$ax+by=1$中，x的最小值

然后exgcd解~

·10+

以后补，现在知识面不足

标签：埃氏,数论,质数,相除,2nd,算法,2022,欧拉
From： https://www.cnblogs.com/tlz-place/p/16723930.html