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

Posted on Edited on In Disqus:

题目

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;
    }
}