The 2021 CCPC Guangzhou Onsite K Magus Night

题目描述

http://codeforces.com/gym/103415/problem/K

简要题意：给定 $n, m, p, q$ ，对于一个长度为 $n$ 的序列 $a_{i}$ ， $a_{i}$ 的每一位都是 $[1, m]$ ，如果整个序列的 $g c d$ 小于等于 $q$ ，且整个序列的 $l c m$ 大于等于 $p$ ，那么这个序列是合法的，每个合法序列的价值是 $\prod_{i = 1}^{n} a_{i}$ ，求所有合法序列的价值的和

$n \leq 998244351, p, q \leq m \leq 2 \times 10^{5}$

Solution

注意到一个序列的 $g c d$ 一定是 $l c m$ 的约数，所以我们考虑直接求 $g_{k}$ 表示 $g c d$ 为 $1$ ， $l c m$ 为 $k$ 的合法序列的价值的和，这样我们再搞一个调和级数的枚举就能求出所有合法的 $g_{x, y}$

对于 $g_{k}$ ，显然我们不太好直接操作，我们考虑求 $f_{k} = \sum_{d | k} g_{d}$ ，即求 $g c d$ 为 $1$ ，且 $l c m$ 是 $k$ 的约数的合法序列的价值的和，我们尝试列一下 $f_{k}$ 的式子

\begin{aligned} f_{k} & = \sum_{i_{1} = 1}^{m} \sum_{i_{2} = 1}^{m} \dots \sum_{i_{n} = 1}^{m} [(i_{1}, i_{2}, \dots, i_{n}) = 1] [[i_{1}, i_{2}, \dots, i_{n}] | k] \prod_{j = 1}^{n} i_{j} \\ = \sum_{d | k} μ (d) (\sum_{d | i, i | k} i)^{n} \\ = \sum_{d | k} μ (d) (d σ (\frac{k}{d}))^{n} \\ = \sum_{d | k} μ (d) d^{n} σ^{n} (\frac{k}{d}) \end{aligned}

显然这个东西我们可以用调和级数的做法算出 $f_{1}$ 到 $f_{m}$ ，然后用作经典的莫比乌斯反演，我们能算出 $g_{k}$ ，但是现在我们注意到我们只计算了 $l c m$ 小于等于 $m$ 的情况，但题目实际要求 $l c m$ 大于等于 $p$ 的情况，正难则反，我们求出只有 $g c d$ 的要求下的所有答案，简单 $l c m$ 小于 $p$ 的即可，所有东西的 $n$ 次方都可以预处理，时间复杂度 $O (n \log n)$

#include <iostream>
#include <algorithm>
#define ll long long
#define maxn 200010
#define INF 1000000000000000000
using namespace std;

const int p = 998244353;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
} 

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

ll n, m, P, Q, f[maxn], g[maxn], a[maxn];
ll in[maxn], dn[maxn], an[maxn];
    
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> P >> Q; init_isp(200000);
    for (int i = 1; i <= m; ++i)
        for (int j = i; j <= m; j += i) d[j] += i;
    for (int i = 1; i <= m; ++i) in[i] = pow_mod(i, n), dn[i] = pow_mod(d[i], n);
    for (int i = 1; i <= m; ++i)
        for (int j = i; j <= m; j += i) f[j] = (f[j] + mu[i] * in[i] % p * dn[j / i]) % p;
    //for (int i = 1; i <= m; ++i) cout << i << " " << f[i] << "\n"; return 0; 
    for (int i = 1; i <= m; ++i)
        for (int j = i; j <= m; j += i) g[j] = (g[j] + mu[j / i] * f[i]) % p;
    //for (int i = 1; i <= m; ++i) cout << i << " " << g[i] << "\n"; return 0; 
    int ans = 0; 
    for (int k = 1; k <= P - 1; ++k)
        for (int i = 1; i * k < P && i <= Q; ++i) ans = (ans - in[i] * g[k]) % p;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= m / i; ++j) a[i] = (a[i] + i * j) % p;
    for (int i = 1; i <= m; ++i) an[i] = pow_mod(a[i], n);
    for (int k = 1; k <= Q; ++k)
        for (int d = 1; d <= m / k; ++d) ans = (ans + mu[d] * an[d * k]) % p;
    cout << (ans + p) % p << "\n";
    return 0;
}