[BZOJ 4916] 神犇和蒟蒻

题目大意

给定 \(n\) ,求: \[ \sum_{i = 1}^{n} \mu(i^2) \\ \sum_{i = 1}^{n} \varphi(i^2) \] 结果对 \(1,000,000,007\) 取模。

\(1 \leqslant n \leqslant 1,000,000,000\)

题目链接

BZOJ 4916

题解

第一问,根据莫比乌斯函数的定义,永远是 \(1\)

对于第二问,考虑杜教筛。记 \(f(i) = \varphi(i^2)\) ,即找到另一函数 \(g\) 使得 \(f * g\)\(g\) 的前缀和都比较好求( \(*\) 表示狄利克雷卷积)。

首先,显然有:\(f(i) = i \varphi(i)\)

\(g(i) = i\)\[ \begin{align} (f * g) (n) &= \sum_{d | n} f(d) \times h(\frac{n}{d}) \\ &= \sum_{d | n} d \times \varphi(d) \times \frac{n}{d} \\ &= n \sum_{d | n} \varphi(d) \\ &= n \times (\varphi * 1) \\ &= n^2 \end{align} \] 发现这个函数的前缀和很简单,于是我们就找到了 \(g\) 。(不看题解哪里知道。。。也算是找到了一个套路)

那么,记 \(F(n)\) 为所求,有: \[ F(n) = \sum_{i = 1}^{n} (f * g)(n) - \sum_{i = 2}^{n} g(i) F(\lfloor \frac{n}{i} \rfloor) \] 即: \[ F(n) = \frac{n(n + 1)(2n + 1)}{6} - \sum_{i = 2}^{n} i F(\lfloor \frac{n}{i} \rfloor) \] 别忘了输出第一问的 \(1\)

最后说一说好像是套路或者说是运算法则之类的东西(\(\times\) 表示普通的乘法): \[ (id \times f) * (id \times g) = id \times (f * g) \]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <map>
#include <algorithm>
const int MAXN = 1000005;
const int MOD = 1000000007;
const int INV2 = 500000004;
const int INV6 = 166666668;
int prime[MAXN], primeCnt;
long long phi[MAXN];
bool notPrime[MAXN];
void linearShaker() {
phi[1] = 1;
notPrime[0] = notPrime[1] = true;
for (int i = 2; i < MAXN; i++) {
if (!notPrime[i]) {
prime[primeCnt++] = i;
phi[i] = i - 1;
}
for (int j = 0; j < primeCnt && i * prime[j] < MAXN; j++) {
notPrime[i * prime[j]] = true;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
} else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
for (int i = 1; i < MAXN; i++) (phi[i] *= i) %= MOD;
for (int i = 2; i < MAXN; i++) (phi[i] += phi[i - 1]) %= MOD;
}
long long pSumID2(long long x) {
return x * (x + 1) % MOD * (2 * x + 1) % MOD * INV6 % MOD;
}
long long sumID1(long long l, long long r) {
return (l + r) % MOD * (r - l + 1) % MOD * INV2 % MOD;
}
long long calc(int n) {
if (n < MAXN) return phi[n];
static std::map<int, long long> sum;
std::map<int, long long>::iterator it;
if ((it = sum.find(n)) != sum.end()) return it->second;
long long res = pSumID2(n);
for (int i = 2, last; i <= n; i = last + 1) {
last = n / (n / i);
res = (res + MOD - calc(n / i) * sumID1(i, last) % MOD) % MOD;
}
return sum[n] = res;
}
int main() {
int n;
scanf("%d", &n);
linearShaker();
puts("1");
printf("%lld\n", calc(n));
return 0;
}