数论分块-JZTXT

数论分块

在P2424偶然学到了这个算法，觉得很有意思，于是单拎出来再学习一下。

数论分块，又叫整数分块，解决 f(n) = \sum_{i=1}^{n}g(i) \times \lfloor \frac{n}{i} \rfloor 一类问题。观察发现 \lfloor \frac{n}{i} \rfloor 是成段出现，比如说 n = 12 时数列是这样的：

12 \ 6\ 4\ 3 \ 2\ 2 \ 1\ 1\ 1 \ 1\ 1 \ 1

设区间的右端点为 r ，r = \frac{n}{\lfloor \frac{n}{l} \rfloor} ，l = r + 1。

证明如下：

\lfloor \frac{n}{l} \rfloor = \lfloor \frac{n}{r} \rfloor \le \frac{n}{r} ，所以 r \le \frac{n}{\lfloor \frac{n}{l} \rfloor} ，因此 r = \frac{n}{\lfloor \frac{n}{l} \rfloor}

有了左右端点后，就可以 O(1) 求块内的答案，总复杂度 O(\sqrt{n})

总结一下，数论分块用于在较优时间复杂度内计算可分为一些块的式子，通过将贡献相同的下标合为一块一起计算块内答案，从而起到优化时间复杂度的作用。

还有一些常用的公式：

\sum_{i=1}^{n}i^2 = \frac{n(n+1)(2n+1)}{6}

\sum_{i=1}^{n}i^3 = (\sum_{i=1}^{n}i)^2

题目

P3935 Calculating

不难发现 f(x) 的值就是 f 的约数个数，然后就是板子。

// 
// #include<bits/stdc++.h>
// #define int long long
// using namespace std;
// void solve(){
//  int ans = 0;
//  int n;
//  scanf("%lld", &n);
//  int r = 1;
//  for(register int l = 1; l <= n; l = r + 1){
//      r = n / (n / l);
//      ans += (r - l + 1) * (n / l);
//  }
//  printf("%lld\n", ans);
//  return;
// }
// signed main(){
//  int T;
//  cin >> T;
//  while(T --){
//      solve();
//  }
// }
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+7;
const int mod = 998244353;
int solve(int n){
    if(n<=1) return n;
    int ans=0;
    int r;
    for(int l=1;l<=n;l=r+1){
        r=n/(n/l);
        ans+=(n/l)*(r-l+1);
    }
    return ans;
}
int query(int n){
    int r;
    int ans = 0;
    for(int l = 1; l <= n; l = r + 1){
        r = n / (n / l);
        ans += (n / l) * (r - l + 1);
        ans %= mod;
    }
    return ans % mod;
}
signed main(){
    int l, r;
    cin >> l >> r;
    cout << (query(r) - query(l - 1) + mod) % mod;
}

P2261 [CQOI2007] 余数求和

式子可以转换成 nk - \sum_{i=1}^{n} i \times \lfloor \frac{k}{i} \rfloor，然后就是板子。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+7;
int query(int n, int k){
    int r;
    int ans = 0;
    for(int l = 1; l <= n; l = r + 1){
        if(k / l == 0) r = n;
        else r = k / (k / l);
        
        if(r > n) r = n;
        ans += (k / l) * (r - l + 1) * (l + r) / 2;
    }
    return n * k - ans;
}
signed main(){
    int n, k;
    cin >> n >> k;
    cout << query(n, k);
}

还有些题鸽到csp之后吧