SP34096 DIVCNTK

Posted on Edited on In Word count in article: 405 Reading time ≈ 1 mins.
Min_25筛好题，~~板子题~~

P34096 DIVCNTK - Counting Divisors (general)

题目大意：

求： \[ S_k=\sum_{i=1}^n\sigma_0(i^k)\mod{2^{64}} \]

Sulotion

观察发现，\(\sigma_0(p^k)=k+1\)，不完全积性函数，很好，满足\(\rm{Min_{25}}\)筛的条件

令：\(F(x)=\sigma_0(x^k)\)，\(f(p)=k+1\)

好了，就可以直接套版子了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;
const ll maxn = 1e7 + 10;
const ll mod = 1e9 + 7;

inline ll __read()
{
    ll x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x * t;
}

ll n, p;
ll sq, tot, pr[maxn], id1[maxn], id2[maxn], w[maxn];
ll cnt, g[maxn];
bool vis[maxn];

inline void init(ll maxn)
{
    for (ll i = 2; i <= maxn; ++i) {
        if (!vis[i]) pr[++cnt] = i;
        for (ll j = 1; j <= cnt && pr[j] * i <= maxn; ++j) {
            vis[i * pr[j]] = 1;
            if (!(i % pr[j])) break;
        }
    }
}

inline ll id(ll x)
{
    if (x <= sq) return id1[x];
    return id2[n / x];
}

ll S(ll x, ll j)
{
    if (pr[j] > x) return 0;
    ll k = id(x);
    ll ans = g[k] - j * (p + 1);
    for (ll i = j + 1; i <= cnt && pr[i] * pr[i] <= x; ++i)
        for (ll e = 1, sp = pr[i]; sp <= x; sp *= pr[i], ++e)
            ans += (p * e + 1) * (S(x / sp, i) + (e > 1));
    return ans;
}

signed main()
{
    init(ll(1e6));

    ll t = __read();
    while (t--)
    {
        tot = 0;
        n = __read(), p = __read();
        sq = sqrt(n);
        for (ll l(1), r; l <= n; l = r + 1) {
            r = n / (n / l);
            w[++tot] = n / l;
            g[tot] = n / l - 1;
            if (w[tot] <= sq) id1[w[tot]] = tot;
            else id2[n / w[tot]] = tot;
        }

        for (ll i = 1; i <= cnt; ++i)
            for (ll j = 1; j <= tot && pr[i] * pr[i] <= w[j]; ++j) {
                ll k = id(w[j] / pr[i]);
                g[j] -= g[k] - i + 1;
            }
        
        for (ll i = 1; i <= tot; ++i) g[i] *= (p + 1);

        printf ("%llu\n", S(n, 0) + 1);
    }
}

还有两道题，一样的，只是手动改一下\(p\)就可以过了

SP26073 DIVCNT1 - Counting Divisors

SP20173 DIVCNT2 - Counting Divisors (square)