质数:也称素数，指的是无法被除1和其他自然数整除的正整数，1不是质数。
质数定理:设一个足够大的正整数x，则不超过x的质数的个数大致为 。
质数的判定:试除法:若有一个合数x，则存在一个能整除x的数t， 。
质数筛:埃式筛法:任意整数x的倍数2x,3x,4x......kx不是质数。
void get_prime(int n){
for(int i=2;i<=n;i++){
if(!book[i]){
prime[++step]=i;
for(int k=1;k*i<=n;k++){
book[k*iA]=1;
}
}
}
}
算术基本定理:任何一个大于1的正整数都能唯一分解成有限个质数的乘积，写作:
注意:1，.
试除法分解质因数:
素数筛法
分解质因数: 适合多组访问数据
void divide(int n){
int sum=0,mo=sqrt(n);
for(int i=1;i<=step;i++){
if(mo1){cnt[++sum]=1,prime_factor[sum]=n;}
for(int i=1;i<=sum;i++){//因为最高为sqrt(n),所以推出循环还要查看是否还有剩余
cout<
约数
向下取整：c++中x/y的原则是”向0取整"，所以在c++当x/y0时，即为向下取整。
向上取整：
取模运算：
将x分为k块，这k块的最大总和：
算术基本定理推论:大于1的正整数的所有正约数集合表示如下:
1.的正约数的个数：
2.的所有正约数的和：
求的正约数:试除法： 注意:
法:先利用质数筛法筛出质数，后分解质因数，然后求各个约数
求每个数的正约数集合:倍速法：对于每个数，对于中以d为约数的数就是的倍数：
void Approximate(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n/i;j++){
approxi[i*j].push_back(i);
}
}
}
每个数的正约数的总和大致为:
整除分块：通过观察可以发现该数有重复部分，是重复区间，可以提却出来优化复杂度。
最大公约数：
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
最小公倍数与最大公约数:
互质：互质 等价于
欧拉函数: 中与 互质的数的个数 ，记为 , (是 懒得改了)
借助容斥原理的思想,不难推出
试除法求欧拉函数：
ll eular(ll sum){
ll mo=sqrt(sum);
ll ans=sum;
for(int i=2;i<=mo;i++){
if(!(sum%i)){
while(!(sum%i)){
sum/=i;
}
ans=ans/i*(i-1);
}
}
if(sum>1){ //别漏了最后这一步
ans=ans/sum*(sum-1);
}
return ans;
}
积数函数(*):
