闲话

字符串能不能滚出 OI 啊？😅

所以今天写点小清新的杜教筛。
凭借已经做过 6/9 的历史，我成功在一晚上切穿了杜教筛专题，快来膜我！

昨天闲话里发生了很奇妙的事情
我不知道为什么
这里 @ 一下 jjdw 是有意义的吧（

杜教筛

发现自己还没写过杜教筛的内容，那就权当帮同学预习吧（

首先这玩意的前置知识是 Dirichlet 卷积，记这个复合为 (*)，正常的点值乘法为 (times)。其实推导式子是不用莫反的。

假设我们有一个积性函数 (f)，定义它的前缀和函数为 (S(f, n) = sum_{i=1}^n f(i))。现在需要解决的是快速算出 (S(f, n))。由 duls 总结的杜教筛对一部分具有特殊性质的 (f) 提供了一种 (O(n^{2/3})) 时间复杂度的解决方案。

具体地，我们构造 (g,htext{ s.t. } h = f * g)。假设我们容易对给定的多个 (k le n text{ s.t. } exists x, k = leftlfloor frac nx rightrfloor) 求得 (S(g, k)) 和 (S(h, k))，我们就可以应用杜教筛。杜教筛的推导如下：

所以就可以按照上面的方式递归了！（一般 (g(1)) 是 (1) 所以可以忽略）

那复杂度是多少呢？应用分析 (Min25) 筛时用到的渐进方式可以得到

因此不预处理的复杂度是 (Oleft(n^{3/4} right)) 的。这里默认记忆化了。

欸你刚才不是说 (2/3) 吗？咋变慢了？
别着急，现在考虑预处理。我们预处理前 (B) 个位置的值，且有 (B ge sqrt n)，复杂度就变成了

取 (B = n^{2/3}) 得到总时间复杂度 (O(n^{2/3}))。

总结一下，杜教筛是一类特殊的递归方案。我们首先选取两个易求前缀和的函数，随后将所求函数 (f) 的前 (n^{2/3}) 个点值求出来，做前缀和，最后记忆化递归，在过程中模拟如上的式子就能得到最终答案了。
还发现，由于杜教筛的记忆化性质，其可以在一次求解中得到 (n) 对应 (O(sqrt n)) 个数论分块点值处的前缀和。因此其时间复杂度应当均摊分析，用于数论分块中时总复杂度没有退化。
重复式子：构造 (g,htext{ s.t. } h = f * g)，

给出几个常见的数论函数：

• 欧拉函数 (varphi(n) = sum_{(d,n) =1} 1)
• 莫比乌斯函数 (mu(n))
• 恒等函数 (text I(n) = 1)
• 元函数 (e(n) = [n = 1])
• 单位函数 (text{id} (n) = n)
• 约数个数函数 (text{d} (n) = sum_{d | n} 1)
• 题面里给的函数 (f(n) = small{我怎么知道})

这里记 (k) 个数论函数 (f) 卷起来的函数为 (f_k)。

给出几个常见的构造：

• $mu * text I = e to f = (f * text I) * mu $ 该变换即莫比乌斯反演。
• (varphi * text I = text {id} to text{id} * mu = varphi)
• (text{id} * text{id} = text{id} times text d)

结合例题来理解吧。

例题

首先是板子。

【模板】杜教筛

给定正整数 (n)，求 (S(varphi, n)) 与 (S(mu, n))。

(n le 10^{11})。

照上式模拟即可。具体看代码。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for ( register int (i) = (a); (i) <= (b); ++(i) )
#define pre(i,a,b) for ( register int (i) = (a); (i) >= (b); --(i) )
using namespace std;
const int N = 5e6 + 10, L = 5e6;
int T, n;

int prime[N], cnt, phi[N], mu[N];
inline void sieve() {
    phi[1] = mu[1] = 1;
    rep(i,2,L) {
        if (phi[i] == 0) prime[++cnt] = i, phi[i] = i - 1, mu[i] = - 1;
        rep(j,1,cnt) {
            int tmp = i * prime[j];
            if (tmp > L) break;
            if (i % prime[j] == 0) {
                phi[tmp] = prime[j] * phi[i]; mu[tmp] = 0;
                break;
            } else 
                phi[tmp] = phi[prime[j]] * phi[i]; mu[tmp] = -mu[i];
        }
    } 
	rep(i,2,L) phi[i] = phi[i-1] + phi[i], mu[i] = mu[i-1] + mu[i];
}

int _phi[N], _mu[N];
inline int getPhi(int x) {
	if (x <= L) return phi[x];
	if (~_phi[n / x]) return _phi[n / x];
	int ret = 1ll * x * (x + 1) >> 1;
	for (int l = 2, r; l <= x; l = r+1) {
		r = x / ( x / l );
		ret -= (r - l + 1) * getPhi(x / l);
	} 
	return _phi[n / x] = ret;
}

inline int getMu(int x) {
	if (x <= L) return mu[x];
	if (~_mu[n / x]) return _mu[n / x];
	int ret = 1;
	for (int l = 2, r; l <= x; l = r + 1) {
		r = x / ( x / l );
		ret -= (r - l + 1) * getMu(x / l);
	} 
	return _mu[n / x] = ret;
}

signed main() {
	sieve(); cin >> T;
	while (T--) {
		cin >> n;
		memset(_phi, -1, sizeof _phi);
		memset(_mu, -1, sizeof _mu);
		cout << getPhi(n) << ' ' << getMu(n) << 'n';
	} 
}

简单的最大公约数

给定 (n,k)，求

[sum^k_{a_1=1}sum^k_{a_2=1}sum^k_{a_3=1}dotssum^k_{a_n=1}gcd(a_1,a_2,a_3,dots,a_n)pmod{ 1000000007} ]

(n,k le 10^{11})。

这里是早就写好了的题解！

DZY Loves Math IV

给定 (n,m)，求

[sum_{i=1}^n sum_{j=1}^m varphi(ij) pmod{1000000007} ]

(n le 10^5, m le 10^9)。

考虑 (n) 比较小，我们可以对每个 (n) 计算答案后求和。

现在的问题是求解

假设 (n = pq)，其中 (p) 是将 (n) 的所有质因子拿出一个来求积的得数。我们有

递归计算即可。边界不再赘述。

由于最终是 (leftlfloorfrac mdrightrfloor) 的形式，所以第二维的取值数是 (O(nsqrt m)) 的。每一层要枚举的总状态数是(O(sqrt n)) 的，因此这一部分的复杂度是 (O(n(sqrt n + sqrt m)))。考虑杜教筛的记忆化形式，边界本质上只需要进行一次杜教筛即可全部求出来。因此总时间复杂度为 (O(n(sqrt n + sqrt m) + m^{2/3}))。
理论复杂度能跑 (10^{11})，本机 O2 加持下跑了 1.61s。

Submission。

神犇和蒟蒻

给定 (n,m)，求

[sum_{i=1}^n mu(i^2) qquad sum_{i=1}^n varphi(i^2) ]

(n le 10^9)。

没啥，放这题就是整点水清凉一下（

(mu) 那个显然答案就是 (1)。
(varphi)……哦想起来了，放这题是因为想告诉你们 (varphi(n^k) = n^{k-1}varphi(n))。挺好用的。

(f(n) = varphi(n) times n)，(f * text{id} = text{id}_2)。剩下的看代码。

Submission。

Lucas的数论

给定 (n)，求

[sum_{i=1}^n sum_{j=1}^n text d(ij) pmod{1000000007} ]

(n le 10^9)。

还记得 约数个数和 那题吗？
直接套那个式子

然后对 (d) 进行数论分块，对 (mu) 采用杜教筛，对 (x,y) 采用二次数论分块。

根据杨卓凡第一小定理(?)可知总时间复杂度为 (O(n^{3/4}))。

Submission。

留着别的题明天写吧。