2019杭电多校第一场 K. Function

Jul 22, 2019 由 小羊

题目想要求

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

首先可以想到，利用 $\lfloor\sqrt[3]{i}\rfloor$ 的不同值进行分块。我们先记 $m=\lfloor\sqrt[3]{n}\rfloor$， 那么原式变为

$\sum_{c=1}^{m} \sum_{i=c^3}^{\min((c+1)^3-1, n)} \gcd(c,i)$

看着那个min比较碍眼，不如考虑当 $c<m$ 的情况，那么有

$H(c)=\sum_{i=c^3}^{(c+1)^3-1} \gcd(c, i) = \sum_{d|c} d \sum_{i=c^3}^{(c+1)^3-1} \left[\gcd(c,i)=d\right]$

看起来有个什么类似于前缀和的东西？再设

$f(n,d) = \sum_{i=1}^{n} \left[ \gcd(d,i) = 1 \right]$

根据莫比乌斯函数的容斥意义容易得到

$f(n,d) = \sum_{g|d} \mu(g) \left\lfloor\frac{n}{g}\right\rfloor$

回到上面那个式子

$\begin{aligned} H(c) &= \sum_{d|c} d \times \left( f\left(\left\lfloor\frac{(c+1)^3-1}{d}\right\rfloor,\frac{c}{d}\right) - f\left(\left\lfloor\frac{c^3-1}{d}\right\rfloor,\frac{c}{d}\right) \right) \\ &= \sum_{d|c} d \sum_{g|\frac{c}{d}} \mu(g) \left( \left\lfloor\frac{(c+1)^3-1}{gd}\right\rfloor - \left\lfloor\frac{c^3-1}{gd}\right\rfloor \right) \\ &= \sum_{gkd=c} d ~\mu(g) \left( \left\lfloor\frac{(c+1)^3-1}{gd}\right\rfloor - \left\lfloor\frac{c^3-1}{gd}\right\rfloor \right) \\ &= \sum_{kt=c} \left( \sum_{gd=t} d ~\mu(g) \right) \left( \left\lfloor\frac{(c+1)^3-1}{gd}\right\rfloor - \left\lfloor\frac{c^3-1}{gd}\right\rfloor \right) \\ &= \sum_{kt=c} \varphi(t) \left( \left\lfloor\frac{(c+1)^3-1}{t}\right\rfloor - \left\lfloor\frac{c^3-1}{t}\right\rfloor \right) \end{aligned}$

好像可以发现 $c | (c+1)^3-1$，那后面那个玩意又有点碍眼，看看好像只有 $t=1$ 的时候不太一样？不如我们……

$\begin{aligned} H(c) &= \sum_{kt=c} \varphi(t) \left( \frac{(c+1)^3-1}{t} - \left\lfloor\frac{c^3}{t} \right\rfloor + 1 \right) \\ &= \sum_{kt=c} \varphi(t)~k~(3c+3) + \sum_{kt=c} \varphi(t)k \\ &= c + 3(c+1) (\varphi * id)(c) \end{aligned}$

那我们继续看后面那部分吧

$\begin{aligned} H'(m) &= \sum_{d|m} d \sum_{i=m^3}^n [\gcd(m,i) = d] \\ &= \sum_{d|m} d \sum_{g|\frac{m}{d}} \mu(g) \left( \left\lfloor\frac{n}{gd}\right\rfloor - \left\lfloor\frac{m^3-1}{gd}\right\rfloor \right) \\ &= \sum_{t|m} \varphi(t) \left( \left\lfloor\frac{n}{t}\right\rfloor - \left\lfloor\frac{m^3-1}{t}\right\rfloor \right) \end{aligned}$

再回去看看最开始要的东西

$H'(m) + \sum_{i=1}^{m-1} H(i)$

不过 $H(i)$ 看起来可以线性筛再前缀和？

好像 $O(n^{\frac{1}{6}})$ 单组询问的复杂度可以接受？Let’s go~

#include <bits/stdc++.h>
typedef long long lld;
using namespace std;
const size_t MAXN = 1e7+5;
const int MOD = 998244353;
bool isnp[MAXN];
int pcn, pri[MAXN/10];
lld g[MAXN], s[MAXN];
int phi[MAXN], q[MAXN];
int mod;

void init_prime()
{
    g[1] = q[1] = phi[1] = 1;

    for (int i = 2; i < MAXN; i++)
    {
        if (!isnp[i])
        {
            g[i] = s[i] = 2*i-1;
            q[i] = i-1;
            phi[i] = i-1;
            pri[pcn++] = i;
        }

        for (int j = 0; j < pcn; j++)
        {
            int k = i * pri[j];
            if (k >= MAXN) break;
            isnp[k] = true;

            if (i % pri[j] == 0)
            {
                s[k] = (s[i] + q[i] + 0ll) * pri[j];
                q[k] = q[i] * pri[j];
                g[k] = g[i] / s[i] * s[k];
                phi[k] = phi[i] * pri[j];
                break;
            }
            else
            {
                phi[k] = phi[i] * (pri[j] - 1);
                q[k] = q[pri[j]];
                s[k] = s[pri[j]];
                g[k] = g[i] * s[k];
            }
        }
    }

    for (int i = 1; i < MAXN; i++)
    {
        g[i] = (g[i-1] + i + (3 * i + 3) * (g[i] % MOD)) % MOD;
    }
}

int two(__int128 n)
{
    if (n < 8) return 1;
    int l = 1, r = 1e9+7, m;
    while (r - l > 1)
    {
        m = (l + r) >> 1;
        if (m > n / m / m)
            r = m;
        else
            l = m;
    }
    return r-1;
}

void solve()
{
    __int128 n = 0;
    char buf[30];
    scanf("%s", buf);
    for (int i = 0; buf[i]; i++)
        n = n * 10 + (buf[i] - '0');
    int m = two(n);
    lld ans = g[m-1];
    __int128 qwq = m; qwq *= m; qwq *= m; qwq -= 1;
    for (int i = 1; i * i <= m; i++)
    {
        if (m % i == 0)
        {
            ans += phi[i] * ((n / i % MOD) - (qwq / i % MOD)) % MOD;
            if (m != i * i)
                ans += phi[m / i] * (n / (m / i) % MOD - (qwq / (m / i) % MOD)) % MOD;
        }
    }
    ans %= MOD;
    if (ans < 0) ans += MOD;
    printf("%lld\n", ans);
}

int main()
{
    init_prime();
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}