2022杭电多校6 B Jo loves counting

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=7186

简要题意：给定 $n$，求 $\frac{1}{n}\sum_{i=1}^nf(i)$，其中 $f(x)$ 是积性函数，且 $f(p^k)=\frac{p^k}{k}$，答案对质数 $4179340454199820289$ 取模

$n\le 10^{12}$

Solution

看到 $f(p^k)$ 的式子，容易想到 $min25$，但是 $10^{12}$ 加上需要用龟速乘导致 $min25$ 等一类亚线性筛跑不动，我们考虑 $PN$ 筛，构造函数 $g(x)=x$，可以求得 $h(p^k)=\frac{p^k}{k\times(k-1)}$，$g(x)$ 的前缀和可以 $O(1)$ 求，那么我们的时间复杂度为 $O(\sqrt n)$

#include <iostream>
#include <cmath>
#define maxn 1000010
#define ll long long
using namespace std;

const ll p = 4179340454199820289;
inline ll mul(ll x, ll y) { return (x * y - (ll) ((long double) x / p * y) * p + p) % p; }
inline ll add(ll x, ll y) { return (x += y) >= p ? x - p : x; }
ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = mul(x, x))
        if (n & 1) s = mul(s, x);
    return s;
}

const int N = 1000000;

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

ll inv[maxn];
void init_inv(int n) {
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) inv[i] = mul(p - (p / i), inv[p % i]);
}

const ll inv2 = pow_mod(2, p - 2);
inline ll F1(ll n) { return mul(n, mul(n + 1, inv2)); } 
inline ll ch(ll pk, int k) { return p - mul(pk, mul(inv[k], inv[k - 1])); }

ll n;

ll dfs(int k, ll m, ll h) {
    ll ans = mul(h, F1(n / m));
    for (ll res = n / m; 1ll * pri[k] * pri[k] <= res && k <= cnt; ++k)
        for (ll e = 2, t = 1ll * pri[k] * pri[k]; t <= res; t *= pri[k], ++e) 
            ans = add(ans, dfs(k + 1, m * t, mul(h, ch(t, e))));
    return ans;
}

void work() {
    cin >> n;
    cout << mul(dfs(1, 1, 1), pow_mod(n, p - 2)) << "\n";
}

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

    int T; cin >> T; init_isp(N); init_inv(N);
    while (T--) work();
    return 0;
}