Htto的小站
0%

数论入门

发表于 更新于 分类于 ，

[toc]

数论分块

对于 \[ \sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor \]

的式子我们使用整除分块来快速计算\(O(\sqrt n)\)

我们发现累加的值成块状分布，设块的左端点为\(l\)，打表得出结论右端点为\(r=\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor\)

1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
    int sum = 0;
    int n;
    cin >> n;
    for (int l = 1, r = 0; l <= n; l = r + 1)
    {
        r = (n / (n / l));
        sum += (r - l + 1) * (n / l);
    }
    return 0;
}

余数之和

给定正整数\(n\)和\(k\)，请计算 \[ G(n,k)=\sum\limits_{i=1}^n{k\;mod\;i} \] 推导: \[ k\; mod\;i=k-\lfloor\frac{k}{i}\rfloor\cdot i \] 然后用整除分块就行

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
const int maxn = 1e5 + 5;
using namespace std;
#define int long long
signed main()
{
    int n, k;
    cin >> n >> k;
    int sum = n * k;
    for (int l = 1, r = 0; l <= n; l = r + 1)
    {
        if (k / l == 0)
            r = n;
        else 
            r = k / (k / l);
        if (r > n)
            r = n;
        int base = k / l;
        sum -= (base * l + base * r) * (r - l + 1) / 2;
    }
    cout << sum << endl;
    return 0;
}