整除分块_v2

整除分块思路整理。

更多是一种分块的思维，相同的 $\left[\frac{n}{i}\right]$ 连续出现，考虑分块，依次计算出相同部分的贡献。

对每一个区间，左端点为 l 时，右端点最大为 n / (n / l)。

问题一

求 $\sum\limits_{i=1}^{k}\left[\frac{n}{i}\right],\ (n\leq10^{14})$

void solve(){
    int n, k; cin >> n >> k;
    int res = 0;
    for(int l = 1, r; l <= k; l = r + 1){
        r = n / (n / l);
        if(r > k) r = k;
        res += (n / l) * (r - l + 1);
    }    
       cout << res << '\n';
}

问题二

求 $\sum\limits_{i=1}^{k}n\%i,\ (n\leq10^{14})$

$$\sum\limits_{i=1}^{k}n\%i=\sum\limits_{i=1}^{k}n-i\times\left[\frac{n}{i}\right]=kn-\sum\limits_{i=1}^{k}i\times\left[\frac{n}{i}\right]$$

void solve(){
    int n, k; cin >> n >> k;
    int res = k * n;
    k = min(k, n);
    for(int l = 1, r; l <= k; l = r + 1){
        r = n / (n / l);
        if(r > k) r = k;
        res -= (n / l) * (l + r) * (r - l + 1) / 2;
    }    
       cout << res << '\n';
}