题目链接：HDU 6588（加强版 LOJ 6686）

本文为加强版题解。

给定正整数 $n$，请你求如下式子的值：

$$ \sum_{i = 1} ^ {n} \gcd(\left\lfloor\sqrt[3]{i}\right\rfloor,i) $$

答案对 $998244353$ 取模。

数据范围：$1 \le n \le 10 ^ {30}$。

Solution

当时订正多校赛题目时，花了一上午时间把这题变毒瘤了（

首先枚举 $\left\lfloor\sqrt[3]{i}\right\rfloor$ 的值 $a$ 得到：

$$ \sum_{a = 1} ^ {\left\lfloor\sqrt[3]{n}\right\rfloor}\sum_{i = 1} ^ {n} [\left\lfloor\sqrt[3]{i}\right\rfloor = a]\gcd(a, i) $$

又因为 $\left\lfloor\sqrt[3]{i}\right\rfloor = a$ 等价于 $a ^ 3 \le i \le (a + 1) ^ 3 - 1$，所以上述式子化为：

$$ \sum_{a = 1} ^ {\left\lfloor\sqrt[3]{n}\right\rfloor}\sum_{i = a ^ 3} ^ {\min\left((a + 1) ^ 3 - 1, n\right)} \gcd(a, i) $$

这样我们把 $1 \sim n$ 分为了若干块，最后一块可能不完整。设 $r = \left\lfloor\sqrt[3]{n}\right\rfloor - 1$，带回原式子得到：

$$ \begin{align*} & \sum_{i = 1} ^ {n} \gcd(\left\lfloor\sqrt[3]{i}\right\rfloor, i) \\ = & \sum_{i = \left\lfloor\sqrt[3]{n}\right\rfloor ^ {3}} ^ {n} \gcd(\left\lfloor\sqrt[3]{n}\right\rfloor, i) + \sum_{a = 1} ^ {r} \sum_{i = a ^ 3} ^ {(a + 1) ^ 3 - 1} \gcd(a, i) \end{align*} $$

考虑一个子问题：

$$ \begin{align*} & \sum_{i = 1} ^ n \gcd(a, i) \\ = & \sum_{d \mid a} d \sum_{i = 1} ^ n [\gcd(a, i) = d] \\ = & \sum_{d \mid a} d \sum_{td \mid i, td \mid a} \mu(t) \\ = & \sum_{T \mid a} \left\lfloor\frac{n}{T}\right\rfloor \sum_{d \mid T} d \cdot \mu\left(\frac{T}{d}\right) \\ = & \sum_{T \mid a} \left\lfloor\frac{n}{T}\right\rfloor \varphi(T) \end{align*} $$

第一个和式

前半部分我们需要求出 $\left\lfloor\sqrt[3]{n}\right\rfloor$ 的所有约数的欧拉函数值。

暴力求解和线性筛的复杂度都是不正确的，它们都没有利用约数之间的有机关系。考虑先得到唯一分解，根据 $\varphi$ 的性质可以 $\text{DFS}$ 求得所有约数的 $\varphi$ 值。

该部分的时间复杂度为 $\mathcal O(n ^ {\frac{1}{6}})$。

第二个和式

依旧按照子问题的推导：

$$ \begin{align*} & \sum_{a = 1} ^ {r} \sum_{i = a ^ 3} ^ {(a + 1) ^ 3 - 1} \gcd(a, i) \\ = & \sum_{a = 1} ^ {r} \sum_{T \mid a} \left(\left\lfloor\frac{(a + 1) ^ 3 - 1}{T}\right\rfloor - \left\lfloor\frac{a ^ 3 - 1}{T}\right\rfloor\right) \cdot \varphi(T) \\ = & \sum_{T = 1} ^ {r} \varphi(T) \sum_{i = 1} ^ {\left\lfloor\frac{r}{T}\right\rfloor} \left(\left\lfloor\frac{(iT + 1) ^ 3 - 1}{T}\right\rfloor - \left\lfloor\frac{(iT) ^ 3 - 1}{T}\right\rfloor\right) \\ = & \sum_{T = 1} ^ {r} \varphi(T) \sum_{i = 1} ^ {\left\lfloor\frac{r}{T}\right\rfloor} 3Ti ^ 2 + 3i + 1 \\ = & \sum_{T = 1} ^ {r} \left(T\varphi(T) \cdot 3 \sum_{i = 1} ^ {\left\lfloor\frac{r}{T}\right\rfloor} i ^ 2 \right) + \left(\varphi(T) \cdot 3 \sum_{i = 1} ^ {\left\lfloor\frac{r}{T}\right\rfloor} i \right) + \left(\varphi(T) \left\lfloor\frac{r}{T}\right\rfloor \right) \end{align*} $$

对于 $10 ^ {21}$ 的数据，直接暴力求解就行了。但是对于 $10 ^ {30}$ 的数据，发现 $\left\lfloor\frac{r}{T}\right\rfloor$ 可以数论分块。我们使用「杜教筛」分别求出 $T \varphi(T)$，$\varphi(T)$ 的前缀和（卷上的函数分别为 $g(x) = x, g(x) = 1$）即可。

该部分的时间复杂度为 $\mathcal O(n ^ {\frac{2}{9}})$。

时间复杂度：$\mathcal O(n ^ {\frac{2}{9}})$。

Code

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <unordered_map>

typedef std::pair<long long, int> pli;
typedef std::pair<long long, long long> pll;

const int LIM = 1e7 + 5;
const int MOD = 998244353, I2 = (MOD + 1) / 2, I6 = (MOD + 1) / 6;

int tot, phi[LIM], s1[LIM], s2[LIM];
bool flg[LIM];
std::vector<int> p;
std::unordered_map<long long, int> S1, S2;

template <class Tp>
void read(Tp &x) {
    char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar());
    for (x = 0; ch >= '0' && ch <= '9'; (x *= 10) += (ch ^ 48), ch = getchar());
}
void add(int &x, int y) {
    (x += y) >= MOD && (x -= MOD);
}
void sub(int &x, int y) {
    (x -= y) < 0 && (x += MOD);
}
void sieve(int n) {
    std::fill(flg + 1, flg + n + 1, true);
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (flg[i]) {
            p.emplace_back(i);
            phi[i] = i - 1;
        }
        for (auto j : p) {
            if (i * j > n) break;
            flg[i * j] = false;
            if (i % j == 0) {
                phi[i * j] = phi[i] * j;
                break;
            } else {
                phi[i * j] = phi[i] * phi[j];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        add(s1[i] = phi[i], s1[i - 1]);
        add(s2[i] = 1LL * i * phi[i] % MOD, s2[i - 1]);
    }
}
int sum1(int x) {
    return 1LL * x * (x + 1) % MOD * I2 % MOD;
}
int sum1(int l, int r) {
    return 1LL * (l + r) * (r - l + 1) % MOD * I2 % MOD;
}
int sum2(int x) {
    return 1LL * x * (x + 1) % MOD * (x + x + 1) % MOD * I6 % MOD;
}
int F1(long long n) {
    if (n <= LIM) return s1[n];
    if (S1.count(n)) return S1[n];
    int ans = sum1(n % MOD);
    for (long long l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        sub(ans, (r - l + 1) % MOD * F1(n / l) % MOD);
    }
    return S1[n] = ans;
}
int F2(long long n) {
    if (n <= LIM) return s2[n];
    if (S2.count(n)) return S2[n];
    int ans = sum2(n % MOD);
    for (long long l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        sub(ans, 1LL * (sum1(r % MOD) - sum1((l - 1) % MOD) + MOD) * F2(n / l) % MOD);
    }
    return S2[n] = ans;
}
int F1(long long l, long long r) {
    int ans;
    sub(ans = F1(r), F1(l - 1));
    return ans;
}
int F2(long long l, long long r) {
    int ans;
    sub(ans = F2(r), F2(l - 1));
    return ans;
}
void dfs(int x, long long n, long long p, std::vector<pli> &fac, std::vector<pll> &phi) {
    if (x == (int)fac.size()) return;
    dfs(x + 1, n, p, fac, phi);
    long long prime = fac[x].first;
    int cnt = fac[x].second;
    n *= prime, p *= prime - 1;
    phi.emplace_back(std::make_pair(n, p));
    dfs(x + 1, n, p, fac, phi);
    for (int i = 2; i <= cnt; i++) {
        n *= prime, p *= prime;
        phi.emplace_back(std::make_pair(n, p));
        dfs(x + 1, n, p, fac, phi);
    }
}
int calc(long long n, __int128 l, __int128 r) {
    l--;
    std::vector<pli> fac;
    std::vector<pll> phi;
    for (int i = 2; 1LL * i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            for (; n % i == 0; n /= i, cnt++);
            fac.emplace_back(std::make_pair(i, cnt));
        }
    }
    if (n > 1) fac.emplace_back(std::make_pair(n, 1));
    phi.emplace_back(std::make_pair(1, 1));
    dfs(0, 1, 1, fac, phi);
    int ans = 0;
    for (auto x : phi) {
        if (x.second >= MOD) x.second %= MOD;
        add(ans, (r / x.first - l / x.first) % MOD * x.second % MOD);
    }
    return ans;
}
int main() {
    sieve(LIM - 5);
    __int128 n;
    read(n);
    if (n < 8) {
        printf("%d\n", (int)n);
        return 0;
    }
    long long m = pow(n, 1.0 / 3);
    for (; (__int128)(m + 1) * (m + 1) * (m + 1) <= n; m++);
    int ans = calc(m, (__int128)m * m * m, n);
    m--;
    for (long long l = 1, r; l <= m; l = r + 1) {
        r = m / (m / l);
        long long x = m / l;
        int xx = x % MOD;
        add(ans, 3LL * F2(l, r) * sum2(xx) % MOD);
        add(ans, 3LL * F1(l, r) * sum1(xx) % MOD);
        add(ans, 1LL * F1(l, r) * xx % MOD);
    }
    printf("%d\n", ans);
    return 0;
}
最后修改：2019 年 07 月 29 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏