Luogu P6156 简单题

题目描述

https://www.luogu.com.cn/problem/P6156

简要题意：求 $\sum_{i=1}^n\sum_{j=1}^n(i+j)^kf((i,j))(i,j)$​，其中 $f(n)$ 当且仅当 $n$ 无平方因子时为 $1$

$n\le 5\times 10^6,k\le 10^{18}$

Solution

先进行套路的莫反

$$\begin{aligned} ans&=\sum_{i=1}^n\sum_{j=1}^n(i+j)^kf((i,j))(i,j)\\ &=\sum_{t=1}^n\sum_{i=1}^n\sum_{j=1}^n(i+j)^ktf(t)[(i,j)=t]\\ &=\sum_{t=1}^n\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{t}\rfloor}t^{k+1}(i+j)^kf(t)\sum_{d|(i,j)}\mu(d)\\ &=\sum_{t=1}^nt^{k+1}f(t)\sum_{d=1}^{\lfloor\frac{n}{t}\rfloor}d^k\mu(d)\sum_{i=1}^{\lfloor\frac{n}{dt}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{dt}\rfloor}(i+j)^k\\ &=\sum_{T=1}^nT^k\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{T}\rfloor}(i+j)^k\sum_{t|T}tf(t)\mu(\frac{T}t) \end{aligned}$$

我们令 $S(n)=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k$，$F(n)=\sum_{i=1}^ni^k$，$G(n)=\sum_{i=1}^nF(i)$，容易得到 $S(n)=G(2n)-2G(n)$

后面那个东西显然是 $\sum_{d|n}d\mu(d)\mu(\frac{n}{d})$，对于 $n=p^k$，当 $k>2$ 时为 $0$，这个东西可以线筛

另外自然数幂和也可以线筛，因为他是完全积性函数

可以做到 $O(n)$ 预处理，单词询问 $O(\sqrt n)$

#include <iostream>
#define maxn 10000010
#define ll long long
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;
} 

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 / 10], cnt, f[maxn], g[maxn], s[maxn]; bool isp[maxn]; 
void init_isp(int n, ll k) {
    f[1] = g[1] = 1; 
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i, f[i] = i - 1, g[i] = pow_mod(i, k);
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            g[i * pri[j]] = mul(g[i], g[pri[j]]);
            if (i % pri[j] == 0) {
                if (i / pri[j] % pri[j])
                    f[i * pri[j]] = mul(f[i / pri[j]], p - pri[j]);
                break;
            }
            f[i * pri[j]] = mul(f[i], pri[j] - 1);
        }
    }
    for (int i = 1; i <= n; ++i) f[i] = add(f[i - 1], mul(g[i], f[i])), s[i] = add(s[i - 1], g[i]);
    for (int i = 1; i <= n; ++i) s[i] = add(s[i], s[i - 1]); 
}

int n;
ll k;

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k; init_isp(2 * n, k); ll ans = 0;
    for (int l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ans = (ans + 1ll * (s[2 * (n / l)] - 2 * s[n / l]) * (f[r] - f[l - 1])) % p;
    }
    cout << (ans + p) % p << "\n";
    return 0; 
}