【题解】51nod-1594-Gcd and Phi

题目

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1594

题意

\[ F(n)=\sum_{i=1}^n\sum_{j=1}^n \varphi(gcd(\varphi(i),\varphi(j))) \]

题解

\(C_k=\sum_{i=1}^n[k=\varphi(i)]\),那么有

$$ \[\begin{eqnarray} F(n) &=& \sum_{i=1}^n\sum_{j=1}^n C_iC_j\varphi(gcd(i,j)) \\ &=& \sum_{d=1}^n \varphi(d) \sum_{i=1}^n \sum_{j=1}^n C_iC_j[gcd(i,j)=d] \\ &=& \sum_{d=1}^n\varphi(d) f(d) \\ g(d) &=& \sum_{d|i} \sum_{d|j} C_i C_j \\ &=& (\sum_{d|i} C_i)^2\\ f(d) &=& \sum_{d|t} \mu(\frac td) g(t) \end{eqnarray}\] $$

在预处理 \(\mu\)\(\varphi\) 后,\(g\)\(f\) 都能在 \(O(n\log n)\) 时间内求得(甚至可以不用算 \(\mu\),直接容斥,详见代码)。

代码

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
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "DBG: " << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int N = 2E6 + 100;

const LL p_max = 2E6 + 100;
LL phi[p_max] = {-1, 1};
void get_phi() {
static bool vis[p_max];
static LL prime[p_max], p_sz, d;
FOR (i, 2, p_max) {
if (!vis[i]) {
prime[p_sz++] = i;
phi[i] = i - 1;
}
for (LL j = 0; j < p_sz && (d = i * prime[j]) < p_max; ++j) {
vis[d] = 1;
if (i % prime[j] == 0) {
phi[d] = phi[i] * prime[j];
break;
}
else phi[d] = phi[i] * (prime[j] - 1);
}
}
}

LL c[N], g[N], f[N];
int main() {
get_phi();
int T; cin >> T;
while (T--) {
memset(c, 0, sizeof c); memset(g, 0, sizeof g); memset(f, 0, sizeof f);
int n; cin >> n;
FOR (i, 1, n + 1) c[phi[i]]++;
FOR (d, 1, n + 1)
for (int i = d; i <= n; i += d)
g[d] += c[i];
FOR (i, 1, n + 1) f[i] = g[i] * g[i];
FORD (d, n, 0)
for (int i = d + d; i <= n; i += d)
f[d] -= f[i];
LL ans = 0;
FOR (i, 1, n + 1) ans += f[i] * phi[i];
cout << ans << endl;
}
}
w