1.整除关系是指，对于两个整数p、q，
有q%p=0，
或存在整数k使得q = k*p,
记作p|q。
整除关系有如下性质:
- 𝑎∣𝑏 ⟺ −𝑎∣𝑏 ⟺ 𝑎∣−𝑏 ⟺ |𝑎|∣|𝑏|
- 𝑎∣𝑏 ∧𝑏∣𝑐 ⟹ 𝑎∣𝑐
- 𝑎∣𝑏 ∧𝑎∣𝑐 ⟺ ∀𝑥,𝑦∈𝐙, 𝑎∣(𝑥𝑏 +𝑦𝑐)
- 𝑎∣𝑏 ∧𝑏∣𝑎 ⟹ 𝑏 = ±𝑎
- 设 𝑚!=0 ,那么 𝑎∣𝑏 ⟺ 𝑚𝑎∣𝑚𝑏
- 设 𝑏!=0 ,那么 𝑎∣𝑏 ⟹ |𝑎| ≤|𝑏|
- 设 𝑎!=0 ,𝑏 =𝑞𝑎 +𝑐 ,那么 𝑎∣𝑏 ⟺ 𝑎∣𝑐
2.规定，若a|b, a是b的约数，b是a的倍数
3.带余除法：设 𝑎,𝑏为两个给定的整数，𝑎!=0. 设𝑑是一个给定的整数．那么，一定存在唯一的一对整数 𝑞 和 𝑟 ，满足 𝑏 = 𝑞𝑎 +𝑟, 𝑑 ≤ 𝑟 < |𝑎| +𝑑.
4.同余关系是指，对于三个整数p、q、r，
有p-q%r=0，
即 p%r = q%r
或p-q|r,
记为p≡q(mod r)
称p与q对r同余
5.质数筛：找出从1到n的所有质数
a.埃氏筛：对每一个大于1的数，其k倍（k为整数）必为合数。
代码实现:
vector<int> prime;
vector<bool> isPrime(n+1, true);void Eratosthenes(int n){isPrime[0] = false, isPrime[1] = false;for(int i = 2; i <= n; i++){if(isPrime[i]) {prime.push_back(i);if ((long long)i * i > n) continue;for(int j = i*i; j <= n; j+=i){if(isPrime[j]) isPrime[j] = false;}}}
}
复杂度nlogn，对于每一个质数i，i * 2到i * (i-1)都已经在之前的质数循环中筛掉了(假设是k * i，k < i，若k为质数，在先前处理质数k时已经筛掉了k * i，若k为合数，则必定在一k的质因数k'时筛掉了k * i)
埃氏筛的优化：上述Eratosthenes函数中，外层循环的筛只需要筛到i*i<=n即可，不需要判断if ((long long)i * i > n) continue;，这是优化到平方根；还可以将2单独提出来，后续只筛奇数的i，循环步长改为i+=2即可，又能减少一半的工作量。经过这两次优化后，时间复杂度被压缩至n loglog sqrt(n)
关于大数据的埃氏筛内存优化，详见todo:分块筛法
b.线性筛(欧拉筛)
埃氏筛中，许多合数被重复标记，而线性筛通过优化使得时间复杂度进一步降低到了O(n)，线性筛的具体做法是，通过判断当前筛的数是否能被已经筛出的质数整除，决定是否继续取出质数筛选，避免重复筛选，代码如下：
vector<int> prime;
vector<int> notPrime(n+1, false);void EulerSieve(int n){for(int i = 2; i <= n; ++i){if(!notPrime[i]) prime.push_back(i);for(int primeJ : prime){if(primeJ * i > n) break;notPrime[primeJ * i] = true;if(i % primeJ == 0) break; /* 如果i能被primeJ整除，说明先前i已经被primeJ筛掉了，后续i的倍数一定也已经被primeJ筛掉，故break*/ }}
}
线性筛的其他应用见todo:线性筛应用