一、同余定理
1.反身性：\(a\equiv a (mod m)\)
2.对称性：若\(a\equiv b(mod m)\)，则\(b\equiv a (mod m)\)
3.传递性：若\(a\equiv b(mod m)\)，\(b\equiv c(mod m)\)，则\(a\equiv c(mod m)\)
4.同余式相加：若\(a\equiv b(mod m)\)，\(c\equiv d(mod m)\)，则\(ac\equiv bd(mod m)\)
5.同余式相乘：若\(a\equiv b(mod m)\)，\(c\equiv d(mod m)\)，则\(ac\equiv bd(mod m)\)
二、最小公倍数与最大公约数
最大公约数：GCD
辗转相除法：设\(gcd(a,b)\)为\(a\)与\(b\)的最大公约数
当\(b\)为0时，此时的\(a\)即为二者的最大公约数
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
最小公倍数：LCM
记\(d=gcd(a,b)\)，\(a=a'd\)，\(b=b'd\)，可以看出\(lcm(a,b)=\frac{ab}{gcd(a,b)}\)
三、整除
给定\(a\),\(b\)两个数，若b能整除a，记作\(b\mid a\)，反之记作\(a\nmid b\)
简单定理：
- 若\(b\mid a\)，且\(c\mid b\)，则\(c\mid a\)
- 若\(c\mid a\)，且\(c\mid b\)，则\(c\mid \left(na+mb\right)\)
四、素数与合数
对于任意一个大于1的自然数，只有1和它本身两个因子，则称为素数
素数定理：小于等于x的素数个数 \(\approx \frac{x}{\ln x}\) ，可以用来估计素数个数，进而估算所开数组的大小
不是素数的大于1的自然数称为合数
素数筛法：
1、暴力枚举
复杂度：\(O(\log{n})\)
由于任意一个数\(x\)的因子可看为两部分，小于\(\sqrt{x}\)与大于\(\sqrt{x}\)，因此可以枚举所有\(\{i\mid i\le \sqrt{x}\}\)，如若出现\(i\mid x\)，则不是素数，反之是素数。
一般用于对某单个数的素性判定
bool check(int x)
{
int end = sqrt(x);
for (int i = 2; i <= end; ++i)
{
if (x % i == 0)
return false;
}
return true;
}
拓展内容（求单个合数的最大质因数）
对于任何一个数\(x\)，可以将他进行质因数分解，且同时保证\(prime[i]^2\le x_{cur}\)进行优化。
首先可以预处理出所有\(\{prime\mid prime \le \sqrt{x}\}\)，这样\(x\)的质因数分解一定是在这个集合中，或者只有最大质因数不在这个集合中。如果所剩下的最后一个数为1，即完美的进行了质因数分解，则最大质因数为最后一次除的质数，反之则最后剩下的数即为最大质因数
const int maxn = 10000;
int vis[maxn];
int cnt, prime[maxn/10];
void Euler_Sieve()
{
for (int i = 2; i < maxn; ++i)
{
if (!vis[i]) prime[cnt++] = i;
for (int j = 0; j < cnt && prime[j] * i < maxn; ++j)
{
vis[prime[j] * i] = true;
if (i % prime[j] == 0)
break;
}
}
}
int Maximum_prime_factor(int x)
{
int ans;
for (int i = 0; i < cnt && prime[i] * prime[i] <= x; ++i)
{
if (x % prime[i] == 0)
{
ans = prime[i];
while (x % prime[i] == 0)
x /= prime[i];
}
}
return x == 1 ? ans : x;
}
2、埃氏筛法
复杂度：\(O(\log{\log{n}})\)
由于对于任何合数而言，他们能够被任意\(prime\) 整除，所以，可以通过枚举\(k*prime(k*prime\le lim_{up})\)，来筛选出一些约数，而没有被筛选过的自然就是素数
值得说明的是：当选中某个\(prime\)时，比\(prime\)小的质数的倍数已经被筛出了，所以为了减小时间复杂度，可以从\(prime^2\)开始筛选
const int maxn = 10000;
bool vis[maxn];
int cnt, prime[maxn / 10];
void Eratosthenes_Sieve()
{
for (int i = 2; i < maxn; ++i)
{
if (vis[i]) continue;
prime[cnt++] = i;
for (int j = i * i; j < maxn; j += i)
vis[j] = true;
}
}
拓展内容（求出多个合数的最大质因数）
利用埃氏筛法是由小质数到大质数的筛选过程，每次大质数筛选时会覆盖之前小质数的结果，因此可以得到实现代码
注意：开始条件从\(i^2\)变为了\(2i\)
#include<cstdio>
const int maxn = 10000;
int vis[maxn];
int cnt, prime[maxn / 10];
void get_Maximum_prime_factors()
{
for (int i = 2; i < maxn; ++i)
{
if (vis[i]) continue;
prime[cnt++] = i;
for (int j = 2*i; j < maxn; j += i)
vis[j] = i;
}
}
3、欧拉筛
复杂度：\(O(n)\)
通过对每个合数，只用其最小的质因数进行筛选的思想，每次将\(cur*prime[i]\)对应的数筛出，为了保证最小的质因数筛出，当\(prime[i]\mid cur\)时，需要break
原因在于设\(cur=k*prime[i]\)，那么如果继续筛即对于
则可以看出来，这个数\(n\)本应该在枚举到数\(k*prime[i+1]\)(比\(cur\)大)被\(prime[i]\)筛出
void Euler_Sieve()
{
for (int i = 2; i < maxn; ++i)
{
if (!vis[i]) prime[cnt++] = i;
for (int j = 0; j < cnt && prime[j] * i < maxn; ++j)
{
vis[prime[j] * i] = true;
if (i % prime[j] == 0)
break;
}
}
}
拓展内容（求出多个合数的最小质因数）
利用欧拉筛每个数都被其最小质因数所筛去
注意：开始条件从\(i^2\)变为了\(2i\)
#include<cstdio>
const int maxn = 10000;
int vis[maxn];
int cnt, prime[maxn / 10];
void get_Maximum_prime_factors()
{
for (int i = 2; i < maxn; ++i)
{
if (!vis[i]) vis[i] = prime[cnt++] = i;
for (int j = 0; j < cnt && prime[j] * i < maxn; ++j)
{
vis[prime[j] * i] = prime[j];
if (i % prime[j] == 0)
break;
}
}
}
4、杜教筛
待学
5、min25筛
待学