如果不太影响理解与运用的证明 或是我不会的证明 就都不计喽
关于数论分块我就不想写了感觉比较基础
线性筛
先来说线性筛
一篇推荐的博客
可 \(O(n)\) 预处理积性函数
常见用法：
- \(f(1)=1\)
- \(f(p)=...\) (一般是直接赋值)
- \(f(p^k)=...\) (一般也是递推的样子)
然后处理出来 \(low_i\) 表示 \(i\) 中最小值因子的指数次幂
具体运算就可以套板子了
点击查看代码
void Euler(int n){s[1]=low[1]=isp[1]=1;//情况1for(int i=2;i<=n;i++){if(!isp[i])p[++cnt]=i,low[i]=i,s[i]=;//情况2for(int j=1;j<=cnt&&i*p[j]<=n;j++){isp[i*p[j]]=1;if(i%p[j]==0){low[i*p[j]]=low[i]*p[j],phi[i*p[j]]=phi[i]*p[j];if(low[i]==i){s[i*p[j]]=;//情况3}else{s[i*p[j]]=s[i/low[i]]*s[low[i]*p[j]];}break;}low[i*p[j]]=p[j],s[i*p[j]]=s[i]*s[p[j]];}}
}
具体题目的例子我就不放了因为后面很多代码中都有不同用法
Dirichlet 卷积
只要知道定义式就好啦
杜教筛
在 \(O(n^\frac{2}{3})\) 的时间复杂度内求积性函数前缀和
关键式子：
最后就是一个递归的形式，里面是整除分块
要使用线性筛预处理一部分，再用 unordered_map 做一下记忆化
写法用 \(phi\) 的前缀和举例
点击查看代码
int getphi(int n){if(n<=N)return sp[n];//线性筛预处理的项if(ansp[n])return ansp[n];//unordered_map记忆化int ans=n*(n+1)/2;//计算f卷gfor(int l=2,r;l<=n;l=r+1){//整除分块r=n/(n/l);ans-=(r-l+1)*getphi(n/l);//递归处理}return ansp[n]=ans;//记忆化
}
例题：
【模板】杜教筛 这个比较简单只是用来理解原理和实现过程
对与杜教筛的第一次练习 bjzx 25-1007 模拟赛 T4 ，自己写的博客，公式推导过程挺详细的，让我理解了具体实现及推导细节，也是从这开始自己学习数论
其他题目也会有这部分内容