SP26037 DIVCNT1

Posted on Edited on In Word count in article: 518 Reading time ≈ 2 mins.
本来是像练习min_25的，但是找错题了。。。

SP26073 DIVCNT1 - Counting Divisors

先看了一眼数据范围\(n\le 2^{63}\)，可以了，这与\(Min\_25\)筛无缘了

题目大意

求： \[ \sum_{i=1}^n\sigma_0(i) \]

问题转化：

\[ \begin{align*} \sigma_0(n)&=\sum_{i=1}^n\left\lfloor\frac ni\right\rfloor\\ &=\sum_{i=1}^n\sum_{j=1}^n[i*j\le n]\\ &=\sum_{i=1}^\sqrt n\sum_{j=1}^{\left\lfloor\frac ni\right\rfloor}1+ \sum_{j=1}^\sqrt n\sum_{i=1}^{\left\lfloor\frac nj\right\rfloor}1-\sum_{i=1}^\sqrt n\sum_{j=1}^\sqrt n 1\\ &=2\sum_{i=1}^\sqrt n\left\lfloor\frac ni\right\rfloor-\left\lfloor\sqrt n\right\rfloor^2 \end{align*} \]

等价于求函数\(y=\frac nx\)直线\(y=\sqrt n\)与直线\(y=1\)与函数图像和坐标轴相交构成的闭合图形内的整点个数

紫色阴影部分即为所求（图是嫖的其他巨佬的）

这样，这道题就变成了一道数点问题

通过在\(Stern-Brocot\)树上寻找斜率，借助单调栈去找一个背包

这部分没太明白，鸽~

Code

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
83
84
85
86
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef __int128 _ll;
const int maxn = 1e7 + 10;
const int 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;
}

struct Point
{
    ll x, y;
    Point(ll x = 0, ll y = 0) : x(x), y(y) {}
    Point operator + (const Point &Temp) const {
        return Point(x + Temp.x, y + Temp.y);
    }
}stk[maxn], L, R, M;

ll n;

inline bool In_R(ll x, ll y) 
{
    return x * y <= n;
}

inline double Slope(ll x)
{
    return (double)n / x / x;
}

inline _ll Slove()
{
    _ll res(0);
    int t(0), rt = cbrt(n);
    stk[++t] = Point(1, 0);
    stk[++t] = Point(1, 1);
    ll m = sqrt(n), x = n / m, y = m + 1;
    while (1) {
        for (L = stk[t--]; !In_R(x + L.x, y - L.y); x += L.x, y -= L.y)
            res += x * L.y + (L.y + 1) * (L.x - 1) / 2;
        if (y <= rt) break;
        for (R = stk[t]; In_R(x + R.x, y - R.y); R = stk[--t]) L = R;

        while (1) {
            M = L + R;
            if (!In_R(x + M.x, y - M.y)) {
                stk[++t] = (R = M);
            } else  {
                if (Slope(x + M.x) <= (double) R.y / R.x) break;
                L = M;
            }
        }
    }
    for (int i = 1; i < y; ++i) res += n / i;
    return res * 2 - 1ll * m * m;
}

void Print(_ll x)
{
    if (!x) return;
    Print(x / 10);
    putchar(x % 10 + '0');
}

signed main()
{
    int T = __read();
    while (T--) {
        n = __read();
        Print(Slove());
        puts("");
    }
    system("pause");
}

后面三道题确实是妥妥的\(\rm{Min_{25}}\)筛了