数论
1.整除定理
若a|b，b|c，则a|c
若a|b，a|c，则a|bm+cn（m,n∈N*）
若am|bm，则a|b (m∈N*)
2.质数
对于一个数，因数只有1和它本身是质数；
2是最小的质数，没有最大的质数
3.最大公约数及最小公倍数
C++:
__gcd(C++11)，gcd(C++17)
__lcm(C++14)，lcm(C++17)
4.分解质因数
把一个数分解成多个质数的乘积的形式
例：84=2^237
5.筛质数
埃氏筛法：时间复杂度：O(nloglogn)
欧拉筛：时间复杂度：O(n)
代码：
bitset<MAXN> isprime;
int prime[MAXN],n,cnt;
void euler(){
isprime.set();
isprime[1]=0;
for(int i = 2; i <= n; ++i){
if(isprime[i]) prime[++cnt] = i;
for(int j = 1; j <= cnt && i * prime[j] <= n; ++j){
isprime[i*prime[j]]=0;
if(i % prime[j] == 0) break;
}
}
}
6.取模
a%b∈[0,n)
同余记作a≡b(mod m)
若a≡b(mod m) 则 b≡a (mod m)
若a≡b(mod m) 且k|c 则a≡b(mod k)
7.逆元
逆元的定义: 在代数系统<S, *>中, 若存在元素a,b ∈ S 且 a * b = 幺元e, 则元素a称为b的左逆元, 元素b称为a的右逆元. 若元素x同时为另一个元素y的左逆元和右逆元则称x是y的逆元. 同理y亦是x的逆元.
代码：
inv[1] = 1;
for(int i = 2; i < p; ++ i)
inv[i] = (p - p / i) * inv[p % i] % p;
8.例题
i.线性筛素数
用欧拉筛即可
ii.快速幂求逆元
利用快读边读边取模，在求逆元即可
组员：我、陈仲安、李青宸、李秉恒、徐铭泽