[SPOJ 5971] LCMSum

题目大意

给定 nn ,求

i=1nlcm(i,  n)\sum_{i = 1}^{n} lcm(i, \; n)

多组询问。

1T300,0001 \leqslant T \leqslant 300,000

1n1,000,0001 \leqslant n \leqslant 1,000,000

题目链接

LCMSUM - Luogu SP5971

SPOJ 5971 - LCMSUM

题解

\begin{align} &\sum_{i = 1}^{n} lcm(i, ;\ n) \\ = &\sum_{i = 1}^{n} \frac{n i}{gcd(i, \; n)} \\ = &n \sum_{i = 1}^{n} \frac{i}{gcd(i, \; n)} \\ = &n \sum_{d | n} \frac{1}{d} \sum_{i = 1}^{n} [gcd(i, \; n) = d] i \\ = &n \sum_{d | n} \frac{1}{d} \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} [gcd(i, \; \lfloor \frac{n}{d} \rfloor) = 1] i d \\ = &n \sum_{d | n} \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} [gcd(i, \; \lfloor \frac{n}{d} \rfloor) = 1] i \\ \end{align}

记后面的和式为 f(i)f(i),由于当 n>1n > 1 时,如果有 gcd(n,  x)=1gcd(n, \; x) = 1,则有 gcd(n,  nx)=1gcd(n, \; n - x) = 1,所以与 nn 互质的数是成对出现的,所以有:

f(i)={1n=1nφ(n)2n>1f(i) = \begin{cases} 1 \qquad n = 1 \\ \frac{n \varphi(n)}{2} \qquad n > 1 \end{cases}

此时答案为 ndnf(d)n \sum_{d | n} f(d),枚举约数,每次询问复杂度大概是 O(n)O(\sqrt{n}),考虑进一步优化。

f(i)f(i) 放回去,d=1d = 1 时补上一个 11,则答案为:

n(dndφ(d)2+1)=n2(dndφ(d)+1)n (\sum_{d | n} \lfloor \frac{d \varphi(d)}{2} \rfloor + 1) = \frac{n}{2} (\sum_{d | n}d\varphi(d) + 1)

发现 g(n)=dndφ(d)g(n) = \sum_{d | n} d \varphi(d) 具有积性,但我不会推式子。。。

虽然做不到 O(n)O(n) 预处理,但 O(nlogn)O(n \log n) 的预处理也够过了。

明明都是小学开始接触的东西,为什么一到了反演,lcm 就比 gcd 复杂了这么多。。。

代码

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
#include <cstdio>
const int MAXN = 1000005;
long long phi[MAXN], f[MAXN];
int prime[MAXN], primeCnt;
bool notPrime[MAXN];
void shaker() {
notPrime[0] = notPrime[1] = true;
phi[1] = 1;
for (int i = 2; i < MAXN; i++) {
if (!notPrime[i]) {
prime[++primeCnt] = i;
phi[i] = i - 1;
}
for (int j = 1; 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++) for (int j = i; j < MAXN; j += i) f[j] += i * phi[i];
}
long long calc(int n) {
return n * (f[n] + 1) / 2;
}
int main() {
shaker();
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
printf("%lld\n", calc(n));
}
return 0;
}