Luogu P4213 【模板】杜教筛（Sum）

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
struct Ele {
    int key, val1, val2;
};
vector<Ele> hx[MOD + 10]; // Find 函数和 Insert 函数是 hash 表的函数，不是文章重点
inline Ele Find(int k) {
    int kmod = k % MOD;
    for (auto i: hx[kmod]) {
        if (i.key == k) {
            return i;
        }
    }
    return Ele{key: INF, val1: INF, val2: INF};
}
inline void Insert(Ele ele) {
    hx[ele.key % MOD].push_back(ele);
}

inline int SumId(int n) {
    return n * (n + 1) / 2;
}
Ele EvaSum(int n) {
    if (n <= MAXn2div3) return Ele{key: n, val1: ola[n], val2: mob[n]};
    Ele ans = Find(n);
    if (ans.key != INF) return ans;
    ans = Ele{key: n, val1: SumId(n), val2: 1};
    for (int il = 2, ir = min(n, (n / (n / il))); ; il = ir + 1, ir = min(n, (n / (n / il)))) {
        Ele query = EvaSum(n / il);
        ans.val1 -= (ir - il + 1) * query.val1;
        ans.val2 -= (ir - il + 1) * query.val2;
        if (ir == n) break;
    }
    Insert(ans);
    return ans;
}

signed main() {
    EvaOlaMob(MAXn2div3);
    GetSum(MAXn2div3, ola);
    GetSum(MAXn2div3, mob);
    Ele ans = EvaSum(n);
    printf("%lld %lld\n", ans.val1, ans.val2);
}