数论
常见筛法
对于任意正整数 \(A\)，存在唯一集合 {\((p_1,q_1),(p_2,q_2),\dots,(p_n,q_n)\)} 满足 \(A=\prod^n_{i=1} {p_i}^{q_i}\)
\(\min(a,b)+\max(a,b)=a+b\)
\(\gcd(a,b)\times\operatorname{lcm}(a,b)=ab\)
埃氏筛
在 \(O(n \log\log n)\) 时间内预处理出 \([1,n]\) 内所有的质数。
\([2,n]\) 进行扫描，未标记则加入质数中，并把倍数标记为合数。
- P7960
埃氏筛思想，将十进制含有 \(7\) 的数看为“类质数”。
- P1835
仍然考虑埃氏筛，扫描每个 \(\le \sqrt{R}\)，并对其在 \([L,R]\) 内的倍数标记为合数。
称为区间筛。
线性筛
\(O(n)\) 计算。
令 \(low(n)\) 表示 \(n\) d的最小质因子，对 \([2,n]\) 扫描，对于 \(i\)，我们枚举所有 \(\le low(i)\) 的质数 \(j\)，并将 \(ij\) 标记为合数。
发现 \(n\) 只会在
可以用来求质因子个数。
\(\phi(n)\) 表示 \([1,n]\) 中与 \(n\) 互质的数。
\(n=\sum_{d|n} \phi(\frac{n}{d})\)
如果 \(\gcd(p,q)=1\)，则 \(\phi(pq)=\phi(p)\phi(q)\),反证法。
模意义
光速乘
ll times(ll a,ll b,ll c){
ull t=(long double)a*b/c+0.5;
ll ans=(ull)a*b-t*c;
if(ans<0) ans+=c;
return ans;
}
逆元
模意义下的除法
\(a\) 的逆元是 \(a\) 在模意义下的倒数，逆元关系相互的。
威尔逊定理
对于质数 \(p\)，有 \(1\times 2\times \dots \times(p-1）\equiv -1(\mod p)\)
费马小定理
\(p\) 为质数：
\(a^{p-1} \equiv 1(\mod p)\)
\(a^{-1} \equiv a^{p-2}\)，用快速幂求
\(p\) 为合数：
欧拉定理
若 \(p \ge 2\) 且 \(\gcd(a,p) =1\) ，则 \(a^(\phi(p)) \equiv 1(\mod p)\)
线性预处理逆元
- \(1\) 的逆元为 \(1\)。
- 让 \(p\) 对 \(i\) 作带余除法，得到 \(p=qi+r(r<i)\)
- 将等式带入
inv[i]=fac[i-1]*ifac[i]
裴属定理
对于所有的 \(ai+bj\)，最小的正整数为 \(\gcd(a,b)\)