DDOSvoid's Blog

Loj 6539. 奇妙数论题

发表于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

题目描述

https://loj.ac/p/6539

简要题意：给定一个长度为 $n$ 的排列 $p$，求 $\sum_{i=1}^n\sum_{j=1}^n(i,j)(a_i,a_j)$

$n\le 10^5$

Solution

首先我们划一下式子，这里扔掉 $(i,j)$，我们采用 $\varphi$ 而不是 $\mu$，能够得到 $\sum_{d=1}^n\varphi(d)\sum_{d|i}\sum_{d|j}(a_i,a_j)$

我们考虑对于一个 $d$，不妨设有 $m$ 个 $a_i$，那么贡献就是 $\sum_{i=1}^m\sum_{j=1}^m(a_i,a_j)$，用类似的式子化简可得 $\sum_{d=1}^n\varphi(d)(\sum_{i=1}^m[d|a_i])^2$

我们考虑一个暴力，暴力枚举 $d$，然后暴力枚举这 $m$ 个 $a_i$，然后对于这些 $a_i$，暴力枚举约数

容易得到时间复杂度为 $O(\sum_{i=1}^n\tau(i)\tau(a_i))$​，根据排序不等式，这个东西就是 $\sum_{i=1}^n\tau^2(i)\thickapprox \frac{1}{\pi^2}n\log^3 n+o(n\log ^2n)$​

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
#include <iostream>
#include <unordered_map>
#include <vector>
#define maxn 1000010
#define ll long long
using namespace std;

const int p = 1000000007;

inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }
inline int mul(int x, int y) { return 1ll * x * y % p; }

int pri[maxn], phi[maxn]; bool isp[maxn]; vector<int> d[maxn];
void init_isp(int n) {
    phi[1] = 1; int cnt = 0;  
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i, phi[i] = i - 1;
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
            phi[i * pri[j]] = phi[i] * (pri[j] - 1); 
        }
    }
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i) d[j].push_back(i); 
}

int n, a[maxn];

int cnt[maxn];
int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; init_isp(n); int ans = 0;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        vector<int> A, use; int sum = 0; 
        for (int j = i; j <= n; j += i) A.push_back(a[j]);
        for (auto u : A) 
            for (auto v : d[u]) if (++cnt[v] == 1) use.push_back(v);
        for (auto t : use) sum = add(sum, mul(phi[t], mul(cnt[t], cnt[t]))), cnt[t] = 0; 
        ans = add(ans, mul(sum, phi[i])); 
    } cout << ans << "\n";
    return 0; 
}