！！！

数论

\(\sum_1^n [i\in prime]=O(\frac{n}{\log n})\)。

算数基本定理是常识。

经典问题：\(\gcd\times\operatorname{lcm}=a\times b\)。

埃氏筛

\(O(n\log\log n)\) 处理出 \(1\sim n\) 的所有质数。

对于所有质数扫描所有倍数。

质数的倒数和为 \(O(\log\log n)\)。

P7960

定义广义埃氏筛来筛出所有不合法的数。\(O(V\log V)\)。

P1835

区间筛，预处理 \(1\sim\sqrt{R}\) 之间的质数，然后直接做。

线性筛

令 \(low(i)\) 代表 \(i\) 的最小质因子，然后咕。

欧拉函数

\(\phi(n)=\sum_1^n [\gcd(i,n)=1]\)

\(n=\sum_{d|n}\phi(\frac{n}{d})\)

咕。

是积性函数。

对于 \(0\le i<pq\)，则 \(i\) 与 \((i\bmod p,i\bmod q)\) 构成双射。

不太会证。

可以用积性函数的性质求 \(\phi(1\sim n)\)。咕。

求 \(\oplus_1^n \gcd(i,n)\)。

\(\sum_1^n [\gcd(i,n)=d]=\phi(\frac{n}{d})\)

线性筛筛欧拉函数，不会。

光速乘

看上去很有意思。

逆元

注意到逆元是一种神奇的双射。

威尔逊定理

\((p-1)!\equiv -1(\bmod p)\)

费马小定理

\(a^{p-1}\equiv 1(\bmod p)\)，when \(p\in prime\) 且 \(a\equiv 0(\bmod p)\) 不成立。

不会证。

\(a^{-1}\equiv a^{p-2}(\bmod p)\)

欧拉定理

对于 \(\gcd(a,p)=1\)，存在 \(a^{\phi(p)}\equiv 1(\bmod p)\)

不会证。

线性求逆元

讲的太快了。

线性阶乘逆元

讲的太快了。

可以在 \(O(n+\log p)\) 的时间内求出 \(\{a_i\}\) 的逆元。

思想和上面很像，不会。

裴蜀定理

\(\gcd(a,b)\) 均可以表示为 \(ai+bj\)，并且 \(ai+bj\) 所能表示出的最小正整数为 \(\gcd(a,b)\)，其中 \(i,j>0\)。

exgcd

不如自学。

正确的。

正确的。

正确的。

不如看 B 站。

正确的。

正确的。

正确的。

都会，不用记。

CRT

不想听了。

对于 \(p\) 进制下的纯循环小数 \(0.a_0a_1\cdots a_{n-1}\)，分数形式为 \(\frac{\sum\limits_{i=0}^{n-1}a_ip^{n-i-1}}{p^n-1}\)。

\(a+b=a\oplus b+2\times (a \& b)\)