学习笔记：数论分块

A9 / 2024-09-04 / 原文

数论分块

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}^{\left\lfloor\frac{n}{i}\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}^{\left\lfloor\frac{n}{i}\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(i^2\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}^{\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}(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://oi-wiki.org/math/number-theory/sqrt-decomposition/

https://www.luogu.com/article/jcsvb4vh