Min_25 筛与杜教筛
杜教筛
\(??\) 是 \(??\) 的前缀和，\(??\), \(??\) 同理。
假设 \(?? × ?? = ?\) ，并且 \(??, ??\) 易求出，\(??\) 难求出。
那么
\[H (??) = \sum_{?? \cdot ??≤??} ??(??) ??(??) = \sum_{??≤??} ??(??) ?? (\frac {??} {??})\\ = f(1)\cdot ??(??) + \sum_{2≤??≤??} ??(??) ??(\frac {??} {??})\]有：
\[f(1)\cdot G(n)=H(n)-\sum_{2≤??≤??} ??(??) ??(\frac {??} {??}) \]整除分块，可以在 \(O(n^{\frac {3}{4}})\) 的时间内计算出 \(??(n)\)
代码按照理解大概可以写成这样：
ll GetSum(int n){
ll ans = H(n);
for(ll l = 2, r; l <= n; l = r + 1) {
r = (n / (n / l));
ans -= (F(r) - F(l - 1)) * GetSum(n / l);
} return ans;
}
时间复杂度证明：
考虑到求 \(S(n)\) 时，需要求出 \(2 \times \sqrt n\) 个 \(S(\lfloor \frac {n}{i} \rfloor)\) 。
由于 \(\lfloor \frac{\lfloor \frac {n}{a}\rfloor}{b} \rfloor =\lfloor \frac {n}{a b} \rfloor\) ，显然所需要求的 \(S(\lfloor \frac {n}{i} \rfloor)\) 数量只有 \(2 \times \sqrt n\) 个。
考虑到整除分块的复杂度，可得总复杂度为：
\[O(\sum_{i=1}^{\sqrt n} \sqrt i+ \sum_{i=1}^{\sqrt n} \sqrt \frac{n}{i})=O(n^{\frac {3}{4}}) \]还可以进一步优化杜教筛，即先线性筛出前 \(m\) 个答案，之后再用杜教筛。
这个优化之后的复杂度是：
\[O(\sum_{i=1}^{\lfloor \frac{n}{m} \rfloor}\sqrt \frac{n}{i}) = O(\frac {n}{\sqrt m}) \]取 \(m=n^{\frac {2}{3}}\) 时，总复杂度为 \(O(n^{\frac {2}{3}})\)
此时预处理复杂度与筛法复杂度相等，为杜教筛的最优复杂度。
\[\]
杜教筛小应用
比如说我们要求 \(g(??)=??(??)\times ??\) 的前缀和
那么观察 \(?? * ???? = ????^2\) ，就令 \(?? = ????\)，\(? = ????^2\) 即可。
比如说我们要求 \(g(??)=?? (??) \times ??^??\) 的前缀和
那么观察 \(?? * ????^?? = ????^{??+1}\) ，就令 \(?? = ????^??\)，\(? = ????^{??+1}\) 即可。
比如说我们要求 \(g (??) = ?? (??) \times ??^??\) 的前缀和
那么观察 \(?? * ????^?? = ????^??? ?? = ??\)，就令 \(?? = ????^??\)，? = ?? 即可。
\[\]
例题：
【模板】杜教筛（Sum）
求 \(\sum_{i=0}^{n} \mu(i)\) ：
发现 \(\mu * I = e\)
有：
\[I(1) \cdot \sum_{i=1}^{n}\mu(i)=\sum_{i=1}^{n}e(i)-\sum_{i=2}^{n}I(i)\sum_{j=1}^{\lfloor \frac{n}{i} \rfloor}\mu(t) \]\[\sum_{i=1}^{n}\mu(i)=1-\sum_{i=2}^{n}I(i)\sum_{j=1}^{\lfloor \frac{n}{i} \rfloor}\mu(t) \]\[ans(n)=1-\sum_{i=2}^{n}I(i)\cdot ans(\lfloor \frac{n}{i} \rfloor) \]求 \(\sum_{i=0}^{n} \varphi (i)\)：
发现 \(\varphi * I = id\)
有：
\[I(1) \cdot \sum_{i=1}^{n}\varphi (i)=\sum_{i=1}^{n}id(i)-\sum_{i=2}^{n}I(i)\sum_{j=1}^{\lfloor \frac{n}{i} \rfloor}\varphi (t) \]\[\sum_{i=1}^{n}\varphi (i)=\sum_{i=1}^{n}i-\sum_{i=2}^{n}I(i)\sum_{j=1}^{\lfloor \frac{n}{i} \rfloor}\varphi (t) \]\[ans(n)=\frac{n * (n+1)}{2}-\sum_{i=2}^{n}I(i)ans(\lfloor \frac{n}{i} \rfloor) \]点击查看代码
P3768 简单的数学题
求：
\[\sum_{i=1}^{n}\sum_{j=1}^{n} i\cdot j \cdot gcd(i,j) \]枚举 \(gcd\) ：
\[\sum_{d=1}^{n}d \cdot \sum_{i=1}^{n}\sum_{j=1}^{n} i\cdot j \cdot [gcd(i,j)=d] \]\[\sum_{d=1}^{n}d^3 \cdot \sum_{i=1}^{n/d}\sum_{j=1}^{n/d} i\cdot j \cdot [gcd(i,j)=1] \]\[\sum_{d=1}^{n}d^3 \cdot \sum_{i=1}^{n/d}\sum_{j=1}^{n/d} i\cdot j \cdot \sum_{k|gcd(i,j)}\mu(k) \]\[\sum_{d=1}^{n}d^3 \cdot \sum_{k=1}^{n/d}\mu(k)\cdot \sum_{k|i}^{n/d}\sum_{k|j}^{n/d} i\cdot j \]\[\sum_{d=1}^{n}d^3 \cdot \sum_{k=1}^{n/d}\mu(k)*k^2\cdot \sum_{i=1}^{n/id}\sum_{j=1}^{n/id} i\cdot j \]\[\sum_{d=1}^{n}d^3 \cdot \sum_{k=1}^{n/d}\mu(k)*k^2\cdot (\sum_{i=1}^{n/id} i)^2 \]\[\]
Min_25 筛
对于满足一下条件的积性函数 \(??\) ，如果其满足一下两条件，那么可以快速计算 \(??\) ：
-
\(?? (??)\) 是关于 \(??\) 的低阶多项式。
-
\(??(??^??)\) 有快速计算的方法。
比如 \(?? (??) = ?? ? 1\)，\(?? (??^??) = (?? ? 1) ??^{???1} = ?? (??^{???1})? ??\)
时间复杂度为 \(O(\frac{n^{\frac{3}{4}}}{log\ n})\)，空间复杂度为 \(O(\sqrt n)\)
step 1：
对于每一个 \(x=\lfloor \frac{n}{i} \rfloor\)，求出：
\[\sum_{i=1}^{x}[i \in prime ]\cdot i^k \]令：
\[G(n,i)=\sum_{j=1}^{n}[j \in prime | div(j)>pri_i]\cdot i^k \]其中 \(div(j)\) 表示 \(j\) 的最小质因子。
\(G(n,i)\) 即为 \(≤n\) 且在埃氏筛第 \(i\) 轮后未被筛去的数的 \(k\) 次方和。
一个合数 \(x\ (x≤n)\) ，一定含有 \(≤\sqrt n\) 的质因子，因此若令 \(cnt\) 表示 \(≤n\) 的质数个数，\(G(n,cnt)\) 即为所求。
考虑递推求 \(G(n,i)\)：
若 \(pri_i^2>n\) ，则第 \(i\) 轮不会删除任何数 ，有 \(G(n,i)=G(n,i-1)\)
若 \(pri_i^2≤n\)，则第 \(i\) 轮会删除的数的 \(k\) 次方和即为 \(pri_i^k\times (G(\lfloor \frac {n}{pri_i} \rfloor,i-1)-\sum_{j=1}^{i-1}\limits pri_j^k)\)
因此，有：
\[G(n,i)=\begin{cases} \ \sum_{j=1}^{n}\limits j^k \\ G(n,i-1) \\ G(n,i-1)-pri_i^k\times (G(\lfloor \frac {n}{pri_i} \rfloor,i-1)-\sum_{j=1}^{i-1}\limits pri_j^k) \end{cases}\ \ \ \begin{matrix} (i=0) \\ (pri_i^2>n) \\ (pri_i^2≤n) \end{matrix} \]在储存时，由于 \(\lfloor \frac{n}{i} \rfloor\) 的种类数不超过 \(2\times \sqrt n\) 种
因此可以开两个数组 \(ind1,ind2\) 将这 \(2\times \sqrt n\) 个数离散化，若 \(\lfloor \frac{n}{i} \rfloor ≤ \sqrt n\) 则将其存在 \(ind1[\lfloor \frac{n}{i} \rfloor]\) 处，否则将其存在 \(ind2[\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor]\) 处。
最终可以递推出 \(G(n,cnt)\) ，代码大致如下：
ll r=0;
for(ll l = 1; l <= n; l = r + 1) {
r = n / (n / l); w[++tot]= n / l;
g[tot] = n / l;
g[tot] = (g[tot] * (g[tot] + 1) * inv2 - 1);
if( n / l <= B ) ind1[n / l] = tot;
else ind2[n / (n / l)] = tot;
}
for(int i = 1; i <= top; i++) {
for(int j = 1; j <= tot && pri[i] * pri[i] <= w[j]; j++) {
int k = w[j] / pri[i] <= B ? ind1[w[j] / pri[i]] : ind2[n / (w[j] / pri[i])];
g[j] = (g[j] - pri[i] * (g[k] - sum[i - 1]));
}
}
step 2：
定义 \(S(n,i)=\sum_{j=1}^{n}[div(j)>=pri_i]\cdot f(j)\)，显然，最后答案就是 \(S(n,1)+f(1)\) 。
其中，对于 \(S(n,i)\) 质数的贡献为 \(\sum_{k}\limits G^k(n)\cdot [x^k]f(i)-\sum_{j=1}^{i-1}\limits pri_j\)
对于合数，我们枚举它的最小质因子，以及最小质因子的幂次，贡献为 \(\sum_{j=i}^{pri_j^e≤n}\limits f(pri_j^e)\cdot (S(\lfloor \frac{n}{pri_i^e} \rfloor,j+1)+[e!=1])\)
因此，有：
\[S(n,i)=\begin{cases} 0 \\ \sum_{k}\limits G^k(n)\cdot [x^k]f(i)-\sum_{j=1}^{i-1}\limits pri_j-\sum_{j=i}^{pri_j^e≤n}\limits f(pri_j^e)\cdot (S(\lfloor \frac{n}{pri_i^e} \rfloor,j+1)+[e!=1])\end{cases}\ \ \ \begin{matrix}(pri_i>n)\\(pri_i≤n)\end{matrix} \]简计：
\[S(n,i)=\begin{cases}0\\g[n]-sum[i-1]-\sum_{j=i}^{pri_j^{e+1}≤n}\limits (f(pri_j^e)\cdot S(\lfloor \frac{n}{pri_i^e}\rfloor,j+1)+f(pri_j^{e+1}))\end{cases}\ \ \ \begin{matrix}(pri_i>n)\\ (pri_i≤n)\end{matrix} \]时间复杂度 \(O(\frac{n^{\frac{3}{4}}}{log\ n})\) 或 \(O(n^{1-?})\) ，不需要记忆化。
\[\]
例题：
【模板】Min_25筛
模板题
点击查看代码
```cpp ```#6235. 区间素数个数
点击查看代码
```cpp ```#6053. 简单的函数
点击查看代码
```cpp ```#188. 【UR #13】Sanrd
点击查看代码
```