在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
题目
不难发现 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();
// }
// }