博客园同步

原题链接

前置知识：

莫比乌斯反演，线性筛，狄利克雷卷积，整除分块。

简要题意：

T T T 组询问，求：

∑ i = 1 n μ i \sum_{i=1}^n \mu_i i=1∑n​μi​

∑ i = 1 n ϕ i \sum_{i=1}^n \phi_i i=1∑n​ϕi​

其中， T ≤ 10 T \leq 10 T≤10， n < 2 31 n < 2^{31} n<231.

首先，你需要知道这道题目的 O ( T n n ) O(Tn \sqrt{n}) O(Tnn ​) 算法， O ( T n ) O(Tn) O(Tn) 算法， O ( T + n ) O(T+n) O(T+n) 算法。

显然， O ( T n n ) O(Tn \sqrt{n}) O(Tnn ​) 是暴力， O ( T n ) O(Tn) O(Tn) 是一个个筛， O ( T + n ) O(T+n) O(T+n) 是预处理 线性筛，一个都无法通过。

这题的瓶颈在于，我们 并不需要一个个求出 μ \mu μ 和 ϕ \phi ϕ，可以不拘泥于此。

想想：我们之前求 ∑ i = 1 n ⌊ n i ⌋ \sum_{i=1}^n \lfloor \frac{n}{i} \rfloor ∑i=1n​⌊in​⌋ 的时候，之前手玩 莫比乌斯反演 的时候，甚至有一次玩到 6 6 6 个 ∑ \sum ∑ 还是一一解决了。走过这么多困难，切掉了这么多紫题，这一题怎么就不行了呢？

事实告诉人们，题目从来都是人做出来的。

我们考虑几个简单的卷积：

μ ∗ I = ϵ , ϕ ∗ I = Id , μ ∗ Id = ϕ \mu * \text{I} = ϵ , \phi * \text{I} = \text{Id} , \mu * \text{Id} = \phi μ∗I=ϵ,ϕ∗I=Id,μ∗Id=ϕ

好，根据这些，我们开始了伟大的探索。

假设我们要求一个 积性函数 f f f，可以先不直接求，搞出另一个 g g g，首先考虑怎么求出 f ∗ g f * g f∗g 的前缀和，那样就可以求出 ∑ f \sum_f ∑f​.

根据 莫比乌斯反演 的性质可得：

∑ i = 1 n ( f ∗ g ) ( i ) \sum_{i=1}^n (f*g) (i) i=1∑n​(f∗g)(i)

= ∑ i = 1 n ∑ d ∣ i f ( d ) × g ( i d ) = \sum_{i=1}^n \sum_{d|i} f(d) \times g(\frac{i}{d}) =i=1∑n​d∣i∑​f(d)×g(di​)

= ∑ d = 1 n g ( d ) × ∑ i = 1 ⌊ n d ⌋ f ( i ) = \sum_{d=1}^n g(d) \times \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} f(i) =d=1∑n​g(d)×i=1∑⌊dn​⌋​f(i)

假设 f f f 的前缀和为 S S S，则：

= ∑ d = 1 n g ( d ) S ( ⌊ n d ⌋ ) = \sum_{d=1}^n g(d) S(\lfloor \frac{n}{d} \rfloor) =d=1∑n​g(d)S(⌊dn​⌋)

现在我们要求的是 S ( n ) S(n) S(n).

g ( 1 ) S ( n ) = ∑ d = 1 n g ( d ) S ( ⌊ n d ⌋ ) − ∑ d = 2 n g ( d ) S ( ⌊ n d ⌋ ) g(1) S(n) = \sum_{d=1}^n g(d) S(\lfloor \frac{n}{d} \rfloor) - \sum_{d=2}^n g(d) S(\lfloor \frac{n}{d} \rfloor) g(1)S(n)=d=1∑n​g(d)S(⌊dn​⌋)−d=2∑n​g(d)S(⌊dn​⌋)

显然，因为 g ( 1 ) S ( n ) g(1) S(n) g(1)S(n) 是 d = 1 d=1 d=1 的答案，考虑前缀和相减即可。

此时可以得到：

g ( 1 ) S ( n ) = ∑ d = 1 n ( f ∗ g ) ( d ) − ∑ d = 2 n g ( d ) S ( ⌊ n d ⌋ ) g(1) S(n) = \sum_{d=1}^n (f * g) (d) - \sum_{d=2}^n g(d) S(\lfloor \frac{n}{d} \rfloor) g(1)S(n)=d=1∑n​(f∗g)(d)−d=2∑n​g(d)S(⌊dn​⌋)

那么显然：

S ( n ) = ∑ d = 1 n ( f ∗ g ) ( d ) − ∑ d = 2 n g ( d ) S ( ⌊ n d ⌋ ) g ( 1 ) S(n) = \frac{\sum_{d=1}^n (f * g) (d) - \sum_{d=2}^n g(d) S(\lfloor \frac{n}{d} \rfloor)}{g(1)} S(n)=g(1)∑d=1n​(f∗g)(d)−∑d=2n​g(d)S(⌊dn​⌋)​

此时你会说了，好，这个式子怎么求呢？

这个式子确实难求，但关键是， g g g 函数是我们自己定的，我们可以定一个 g g g 使得 g g g 和 f ∗ g f*g f∗g 的前缀和都非常好算。

好算？联系积性函数的性质，我们想到了： I \text{I} I 和 ϵ ϵ ϵ 都是积性函数，前缀和也非常的简单。后面一堆我们可以整除分块。

先不管怎么定 g g g，伪代码大概长这样：

inline ll sieve(ll n) {
	ll ans=calc(n); //calc(i) 负责计算 (f*g)(i)
	for(ll i=2,r;i<=n;i=r+1) {
		r=(n/(n/i));
		ans-=(sum(r) - sum(i-1)) * sieve(n/i); //sum(i) 计算 g 的前缀和
	} return ans;
}

显然你会发现，这里有递归部分。

递归？这东西，显然会把很多东西重复计算。

因此我们需要 记忆化。

到这里，杜教筛 的样子渐成，我们已经得到了其中的 60 % 60 \% 60%.

下面的难点在于确定 g g g.

入手题目。

f = ϕ f = \phi f=ϕ，令 g = I g = \text{I} g=I，则 f ∗ g = Id f * g = \text{Id} f∗g=Id，此时可以解决。

f = μ f = \mu f=μ，令 g = I g = \text{I} g=I，则 f ∗ g = ϵ f * g = ϵ f∗g=ϵ，此时也可以解决。

好了，现在的问题在于，这东西的时间复杂度如何？

你发现无法通过，因为，杜教筛必须要初始化一部分数据。

假设我们将 n ≤ k n \leq k n≤k 的情况的答案都初始化一遍。那么，经过分析（具体证明） 可得，这样的时间复杂度是：

O ( k + n k ) O(k + \frac{n}{\sqrt{k}}) O(k+k ​n​)

你会发现，只要 O ( k ) O(k) O(k) 不出问题， k k k 越大越好。

显然， k k k 和 n k \frac{n}{\sqrt{k}} k ​n​ 成反比，相等时和最小。（反比例函数知识）

所以， k = n 2 3 k=n^{\frac{2}{3}} k=n32​ 时，时间复杂度达到 O ( n 2 3 ) O(n^{\frac{2}{3}}) O(n32​)，是比较优的。

时间复杂度： O ( T n 2 3 ) O(Tn^{\frac{2}{3}}) O(Tn32​).

实际得分： 100 p t s 100pts 100pts.

博主的代码太丑，不想拿出来了。以后会重构代码发出来的。