数论入门

[toc]

数论分块

对于 $$\sum _{i=1}^n\lfloor \frac{n}{i}\rfloor$$

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

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

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 _{i=1}^{n}kmodi$$ 推导: $$kmodi=k-\lfloor \frac{k}{i}\rfloor \cdot i$$ 然后用整除分块就行

#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;
}