更新日志：
2020.11.07 开坑（ 质数口胡部分）。
2020.11.10 更新一次（约数还没完呢）。
ta还会继续咕咕咕
质数
\(Eratosthenes\)筛(\(O(\sum_{p\in primes}^{n}\frac{n}{p}=n log n)\)：
for(int i=2;i*i<=n;i++)
{
if(Isntpri[i]==0)//是质数
{
for(int j=i*2;j<=n;j+=i){Isntpri[j]++;}
}
}
\(Euler\)筛(\(O(n)\))：
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;
}
}
思考，对于线性的欧拉筛，我们是否可以顺带记录下相应的最小质因子，这样每个和数只会被其最小质因子筛一次，最后找prime数组中的素数达到筛素数的效果。（设\(f_i\)为\(i\)的最小质因子，当且仅当\(f_i=i\)时\(i\)为素数。）
这个思路来自李煜东的《算法竞赛进阶指南》因为思路与题解较有不同，特此提出。
质因数分解：
\(Lemma\):任何一个大于1的正整数都能分解为有限个质数的乘积。
void dvd(int x)
{
int cnt=0;
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0)pri[++cnt]=i,c[cnt]=0;
while(!(n%i))n/=i,c[cnt]++;
}
if(n>1)p[++cnt]=n,c[cnt]=1;
//p为有多少种质因子，c为这些质因子的指数
}
判断质数：
思路类似于质因数分解，直接试除。代吗略。
\(Miller-Robin\)等算法日后可以进行学习。（毕竟是带有随机性的算法）
约数
求约数
我们有这么一个叫做算数基本定理的东西。
其实就是将任何一个大于\(1\)的正整数(\(N\))都可以分解为有限个质数(\(p_i\))的乘积。
\[N=\prod_{i=1}^{m} p_i^{c_i} \]正约数的集合可以是
\[\left\{ p_1^{i_1},p_2^{i_2} … p_m^{i_m}\right\} )(0 \leq i_k\leq c_k) \]那么\(N\)的所有正约数个数则是
\[\prod_{i=1}^m(c_i+1) \]正约数的和则为
\[\prod_{i=1}^m(\sum_{j=0}^{c_i}(p_i)^j) \]然后我们进入算法的学习。
对于求一个数的所有正约数，非常简单，只需要\(O(\sqrt N)\) 扫一遍，每次记录下一对约数($ d & \frac{N}{d}) $ 就可以了。
对于求一个区间，或者是\(1-N\)每个数的正约数集合，我们考虑每个数的倍数必然将这个数作为约数。采用类似筛法的思想可以得出集合。
factors[i*j][++cnt[i*j]]=i;(j<=n/i)
factors[i*j].push_back(i);(j<=n/i)//vector
最大公约数(\(gcd\))
\(gcd\)应该算是基础\(OI\)数学知识中最重要的一项。所以就不讲了吧
还是先给几个定理：
\[\forall a,b \in \mathbb N, gcd(a,b)\times lcm(a,b)=a \times b \]……
同余
……