数论分块
1.0
可以快速计算一些含有除法向下取整的和式（形如 $\sum_{i=1}^n g(i) \left \lfloor \frac{n}{i}\right \rfloor $）。
2.0
引理1：
\(\left \lfloor \frac{n}{i} \right \rfloor\) 的取值最多只有 \(2\times \sqrt n\) 种。
证明：
对于 \(i \le \left \lfloor \sqrt n \right \rfloor\)，显然有 \(\sqrt n\) 种取值。
对于 \(i > \sqrt n\)，有 \(\left \lfloor \frac{n}{i} \right \rfloor \le \left \lfloor \sqrt n \right \rfloor\)，有 \(\sqrt n\) 种取值。
2.1
引理2：
使得 \(\left \lfloor \frac{n}{l} \right \rfloor = \left \lfloor \frac{n}{r} \right \rfloor\) 且满足 \(l \le r \le n\) 的 \(r\) 值最大为 \(\left \lfloor \frac{n}{\left \lfloor \frac{n}{l} \right \rfloor} \right \rfloor\)。
证明：
令 \(k = \left \lfloor \frac{n}{i} \right \rfloor\)，有 \(\left \lfloor \frac{n}{k} \right \rfloor \ge \left \lfloor \frac{n}{\frac{n}{i}} \right \rfloor = i\)。
$ \left \lfloor \frac{n}{\frac{n}{i}} \right \rfloor$ 为满足条件的最大值。
3.0
UVA11526
题意：
多组数据，求 \(\sum_{i=1}^n \left \lfloor \frac{n}{i} \right\rfloor\)。
\(T\le1000 ,n\le 2^{31}-1\)。
解题：
void Work() {
ll n, res = 0;
cin >> n;
for(ll l = 1, r, k; l <= n; l = r+1) {
k = n/l;
r = n/k;
res += k * (r-l+1);
}
cout << res << "\n";
}
P3935
题意：
若 \(x\) 分解质因数结果为 \(x=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}\)，令\(f(x)=(k_1+1)(k_2+1)\cdots (k_n+1)\)，求 \(\sum_{i=l}^rf(i)\) 对 \(998\,244\,353\) 取模的结果。
\(1\le l \le 10^{14}\)，\(1\le r \le 1.6\times 10^{14}\)，\(r-l>10^{14}\)。
解题：
引理1：
若 \(x\) 分解质因数结果为 \(x=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}\)，则 \(f(x)\) 为 \(x\) 的因数个数。
证明：
对于 \(x\) 的一个因数 \(y\)，将其必定能表示为 \(y=p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n}\)。
且每个 \(a_i\) 有 \([0, k_i]\) 共 \(k_i+1\) 种取值。
故 \(x\) 的因数个数为 \((k_1+1)(k_2+1)\cdots (k_n+1)\)。
引理2：
\(1\) 至 \(n\) 中，含有因子 \(d(1\le d\le n)\) 的数的个数为 \(\left \lfloor \frac{n}{d} \right \rfloor\)。
证明略。
所以题目要求的即是 \(\sum_{i=1}^r \left \lfloor \frac{r}{i} \right\rfloor - \sum_{i=1}^{l-1} \left \lfloor \frac{l-1}{i} \right\rfloor\)。套板子即可。
P2261
题意：
求 \(\sum_{i=1}^nk \bmod i,1\le n,k \le 10^9\)。
解题
\(\sum_{i=1}^n k \bmod i = \sum_{i=1}^n k - \left \lfloor \frac{k}{i} \right \rfloor \times i = n \times k - \sum_{i=1}^n \left \lfloor \frac{k}{i} \right \rfloor \times i\)。
考虑怎么求出 \(\sum_{i=1}^n \left \lfloor \frac{k}{i} \right \rfloor \times i\)。
对于一段区间，其值一定，考虑求 \(\sum_{i=l}^r d\times i\)，用等差数列求和公式即可，首项为 \(l\times d\)，末项为 \(r\times d\)，项数为 \(r-l+1\)。
code:
#include<iostream>
#include<cstdio>
#define F(i, l, r) for(int (i) = (l); (i) <= (n); (i) ++)
#define ll long long
using namespace std;
ll n, k;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> k;
ll res = 0;
for(ll l = 1, r, d; l <= n; l = r+1) {
d = k/l;
if(!d) break;
r = min(k/d, n);
//注意边界
res += (r-l+1) * (l + r) * d / 2;
}
cout << n*k - res << "\n";
return 0;
}
P2260
题意 ：
求 \(\sum_{i=1}^n \sum_{j=1}^m(n \bmod i) \times (m \bmod j), i \ne j\)。
\((1\le n,m\le10^9)\)。
解题：
原式 \(= \sum_{i=1}^n(n \bmod i) \times \sum_{j=1}^m(m \bmod j) - \sum_{i=1}^{\min(n,m)}(n\bmod i)\times(m\bmod i)\)
\(= \sum_{i=1}^n(n-\left\lfloor \frac{n}{i} \right\rfloor\times i) \times \sum_{j=1}^m(m-\left\lfloor \frac{m}{i} \right\rfloor\times i) - \sum_{i=1}^{\min(n,m)}(n-\left\lfloor \frac{n}{i}\right\rfloor\times i)\times(m-\left\lfloor\frac{m}{i}\right\rfloor\times i)\)
前面部分同上题，考虑如何求最后一部分。
\(\sum_{i=1}^{\min(n,m)}(n-\left\lfloor \frac{n}{i}\right\rfloor\times i)\times(m-\left\lfloor\frac{m}{i}\right\rfloor\times i)\)
\(=\sum_{i=1}^{\min(m,n)}(nm-n\left\lfloor\frac{m}{i}\right\rfloor\times i - m\left\lfloor\frac{n}{i}\right\rfloor\times i+\left\lfloor\frac{n}{i}\right\rfloor \left\lfloor\frac{m}{i}\right\rfloor\times i^2)\)。
发现只有最后一项不好求，我们有：
\(\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}\)
证明：
\(\sum_{i=1}^n i^2 = \sum_{i=1}^ni(i-1)+i = \sum_{i=1}^n 2\times\binom{i}{2} +i\)
接着逆用帕斯卡公式：\(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\)。
\(2\times\sum_{i=1}^n \binom{i}{2} = 2\times \binom{n+1}{3} = \frac{n(n+1)(n-1)}{3}\)
代入原式，得
\(\sum_{i=1}^n i^2 = \sum_{i=1}^ni(i-1)+i = \sum_{i=1}^n \binom{i}{2} +i = \frac{n(n+1)(n-1)}{3} + \frac{n(n+1)}{2} = \frac{n(n+1)(2n+1)}{6}\)
code
#include<bits/stdc++.h>
#define F(i, l, r) for(int (i) = (l); (i) <= (n); (i) ++)
#define ll long long
#define i128 __int128
using namespace std;
const ll mo = 19940417;
ll calc(ll n) {
ll res = n * n;
for(ll l = 1, r, d; l <= n; l = r+1) {
d = n/l;
r = n/d;
res -= d * (l+r) * (r-l+1) / 2;
}
return res % mo;
}
ll funa(ll l, ll r) {
return ((i128)(l+r) * (r-l+1) / 2 % mo);
}
ll func(ll x) {
return ((i128)x * (x+1) * (2*x+1) / 6 % mo);
}
ll funb(ll l, ll r) {
return ((func(r) - func(l-1)) % mo + mo) % mo;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n, m;
cin >> n >> m;
ll a = calc(n), b = calc(m);
ll w = min(n, m);
ll c = n * m % mo * w % mo;
for(ll l = 1, r, d; l <= w; l = r+1) {
ll num1 = n/l, num2 = m/l;
r = min(n/num1, m/num2);
c = ((c -
funa(l, r) * ((m*num1 + n*num2) % mo)%mo
+ (funb(l, r) * num1 % mo * num2 % mo )%mo) %mo + mo)%mo;
}
cout << ((a * b % mo - c) % mo + mo) % mo;
return 0;
}
P3636
题意：
求在三维坐标系中所有满足 \(a\le x\times y\times z \le b\) 的点 \((x,y,z)\) 到原点的曼哈顿距离的平方和。
数据范围：\(1\le a,b\le 3\times 10^8\)。
解题：
为了方便我们将 \(x,y,z\) 三个数均限制在正整数范围内，三个数乘积为正有两负一正和全正共 \(\binom{3}{2} + 1 = 4\) 种情况，所以最终答案乘 \(4\) 即可。
容易想到将询问进行差分，所以我们考虑求 \(\sum_{i=1}^{n}\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}\sum_{k=1}^{\left\lfloor\frac{n}{i\times j}\right\rfloor}(i+j+k)^2\) 即可。
$ \begin{aligned}\sum_{i=1}{n}\sum_{j=1}\right\rfloor}\sum_{k=1}^{\left\lfloor\frac{n}{i\times j}\right\rfloor}(i+j+k)^2 &=\sum_{i=1}{n}\sum_{j=1}\right\rfloor}\sum_{k=1}^{\left\lfloor\frac{n}{i\times j}\right\rfloor}i^2 + (j+k)^2 + 2ij + 2ik \&= \sum_{i=1}n(i2\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}\left\lfloor\frac{n}{i\times j}\right\rfloor + 2i\sum_{j=1}{\left\lfloor\frac{n}{i}\right\rfloor}\sum_{k=1}\right\rfloor}(j+k)+\sum_{j=1}{\left\lfloor\frac{n}{i}\right\rfloor}\sum_{k=1}\right\rfloor}(j+k)^2)\end{aligned}$
容易发现 \(\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}\left\lfloor\frac{n}{i\times j}\right\rfloor,\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}\sum_{k=1}^{\left\lfloor\frac{n}{i\times j}\right\rfloor}(j+k),\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}\sum_{k=1}^{\left\lfloor\frac{n}{i\times j}\right\rfloor}\) 这三部分用数论分块都是好维护的。
所以我们数论分块套数论分块维护即可。
由于时间限制，应尽量减少取模次数。
code:
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll mo = 10007;
ll inv2, inv6;
struct node{
ll ans1, ans2, ans3;
};
ll Pow(ll a, ll b) {
ll res = 1;
for(; b; b>>=1) {
if(b&1) res = res * a % mo;
a = a * a % mo;
}
return res;
}
inline ll funa(ll l, ll r) {
return (l+r) * (r-l+1) %mo * inv2 %mo;
}
inline ll ready(ll x) {
return x * (x+1) % mo * (2*x+1) % mo * inv6 % mo;
}
inline ll funb(ll l, ll r) {
return ((ready(r) - ready(l-1)) % mo + mo)% mo;
}
node work2(ll n) {
ll ans1 = 0, ans2 = 0, ans3 = 0;
for(ll l = 1, r, d; l <= n; l = r+1) {
d = n/l;
r = n/d;
ans1 = (ans1 + (r-l+1) * d ) % mo;
ans2 = (ans2 + funa(l, r) * d + (r-l+1) * funa(1, d)) % mo;
ans3 = (ans3 + funb(l, r) * d + (r-l+1) * funb(1, d) + 2 * funa(l, r) * funa(1, d)) % mo;
}
node u;
u.ans1 = ans1;
u.ans2 = ans2;
u.ans3 = ans3;
return u;
}
ll work(ll n) {
ll ans = 0;
for(ll l = 1, r, d; l <= n; l = r+1) {
d = n/l;
r = n/d;
node u = work2(d);
ll ans1 = u.ans1, ans2 = u.ans2, ans3 = u.ans3;
ans = (ans + funb(l, r)*ans1 + funa(l, r)*2ll*ans2 + (r-l+1)*ans3) % mo;
}
return ans;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll a, b;
cin >> a >> b;
inv2 = Pow(2, mo-2);
inv6 = Pow(6, mo-2);
cout << (work(b) - work(a-1) + mo) * 4ll%mo;
return 0;
}
参考资料：
https://www.cnblogs.com/rickylin/p/17790471.html
https://oi-wiki.org/math/number-theory/sqrt-decomposition/
https://www.cnblogs.com/mangoworld/p/Number-Theory-Block.html
https://www.luogu.com/article/jcsvb4vh
标签：lfloor,right,frac,分块,数论,sum,笔记,rfloor,left From： https://www.cnblogs.com/SLDS/p/18395851