本文将介绍下取整常用处理方法。不细讲。

整除分块

对于式子 $\sum _i\lfloor \frac{a}{i}\rfloor$，是一系列分数取整求和，其中分母是求和枚举变量。此时就可以使用整除分块。时间复杂度 $O(\sqrt{n})$。（一维整除分块）

原理是 $\lfloor \frac{n}{i}\rfloor$ 最多只有 $2\sqrt{n}$ 个取值。

对于式子 $\sum _i\sum _j\lfloor \frac{a}{i}\rfloor \lfloor \frac{b}{i}\rfloor$，使用二维整除分块。相当于两个下取整的断点只有 $4\sqrt{n}$ 个，时间复杂度为 $O(\sqrt{n})$。实际上可以推广到 $m$ 维整除分块，时间复杂度为 $O(m\sqrt{n})$。

还有式子 $\sum _i\lfloor \frac{n}{ai+b}\rfloor$，此时也可使用整除分块。

例题1

P2260 [清华集训2012] 模积和

求

$$\sum _{i=1}^n\sum _{j=1}^m(n\mathrm{mod}i)\times (m\mathrm{mod}j),i\ne j$$

$\mathrm{mod}19940417$ 的值。

---

这里有一个常用技巧：$a\%b=a-b\lfloor \frac{a}{b}\rfloor$

这里把式子变成
$$\left(\sum _{i=1}^n(n-i\lfloor \frac{n}{i}\rfloor \right)\left(\sum _{j=1}^m(m-i\lfloor \frac{m}{i}\rfloor )\right)$$

左右两边分别处理。

由于 $n-i\lfloor \frac{n}{i}\rfloor$ 中有下取整，且分母是 $i$，所以可以使用整除分块。时间复杂度 $O(\sqrt{n})$

一些恒等式

下面给出几个下取整恒等式。

• 若 $\gcd (a,b)=1$，则有 $2\sum _{i=0}^{b-1}\lfloor \frac{ia}{b}\rfloor =(a-1)(b-1)$
• 对于正整数 $n,m,a,b(a>b)$，有 $\sum _{i=0}^{m-1}\lfloor \frac{n+ia+b}{ma}\rfloor =\lfloor \frac{n+b}{a}\rfloor$
• 对于 $x\in \mathbb{R},n\in {\mathbb{N}}^{+}$，有 $\sum _{i=0}^{n-1}\lfloor x+\frac{i}{n}\rfloor =\lfloor nx\rfloor$

例题2

$$\sum _{i=1}^b\sum _{j=1}^b\lfloor \frac{ija}{b}\rfloor$$

其中 $b\mid n,b\mid m$
$T$ 组数据
答案 $\mathrm{mod}998244353$

---

我们先看如何求 $\sum _{i=1}^n\lfloor \frac{ia}{b}\rfloor$，其中 $b\mid n$

首先求 $g=\gcd (a,b)$，原式化为 $\sum _{i=1}^n\lfloor \frac{i{a}^{\prime }}{b^{\prime }}\rfloor$，其中 $a^{\prime }=\frac{a}{g},b^{\prime }=\frac{b}{g}$。

因为 $b\mid n$，所以 $\sum _{i=1}^n\lfloor \frac{i{a}^{\prime }}{b^{\prime }}\rfloor =\sum _{j=0}^{\frac{n}{b^{\prime }}-1}\sum _{i=1}^{b^{\prime }}\lfloor \frac{a^{\prime }(i+j{b}^{\prime })}{b^{\prime }}\rfloor =\sum _{j=0}^{\frac{n}{b^{\prime }}-1}\sum _{i=1}^{b^{\prime }}\left(\lfloor \frac{i{a}^{\prime }}{b^{\prime }}\rfloor +j{a}^{\prime }\right)=\frac{n{a}^{\prime }\left(n-b^{\prime }\right)}{2b^{\prime }}+\frac{n}{b^{\prime }}\sum _{i=1}^{b^{\prime }}\lfloor \frac{i{a}^{\prime }}{b^{\prime }}\rfloor$

问题转为求 $\sum _{i=1}^{b^{\prime }}\lfloor \frac{i{a}^{\prime }}{b^{\prime }}\rfloor$

由结论 $1$ 得 $\sum _{i=1}^{b^{\prime }}\lfloor \frac{i{a}^{\prime }}{b^{\prime }}\rfloor =\frac{(a^{\prime }-1)(b^{\prime }-1)}{2}+a^{\prime }$

$\sum _{i=1}^n\lfloor \frac{ia}{b}\rfloor =\frac{n{a}^{\prime }\left(n-b^{\prime }\right)}{2b^{\prime }}+\frac{n}{b^{\prime }}\left(\frac{a^{\prime }(b^{\prime }+1)}{2}-\frac{b^{\prime }-1}{2}\right)=\frac{n\left(a^{\prime }n+a^{\prime }-b^{\prime }+1\right)}{2b^{\prime }}=\frac{n\left(an+a-b+\gcd (a,b)\right)}{2b}$

---

看回原题

$\sum _{i=1}^n\sum _{j=1}^m\lfloor \frac{ija}{b}\rfloor =\sum _{i=1}^n\frac{m\left(iam+ia-b+\gcd (ia,b)\right)}{2b}=-\frac{mn}{2}+\frac{mna\left(m+1\right)\left(n+1\right)}{4b}+\frac{m}{2b}\sum _{i=1}^n\gcd (ia,b)$

易得 $\sum _{i=1}^n\gcd (ia,b)=g\sum _{i=1}^n\gcd (i{a}^{\prime },b^{\prime })=g\sum _{i=1}^n\gcd (i,b^{\prime })$

同时 $\sum _{i=1}^n\gcd (i,b^{\prime })=\frac{n}{b^{\prime }}\sum _{i=1}^{b^{\prime }}\gcd (i,b^{\prime })$，因为 $\gcd (i,b^{\prime })=\gcd (i+b^{\prime },b^{\prime })$

$\sum _{i=1}^{b^{\prime }}\gcd (i,b^{\prime })=\sum _{d\mid b^{\prime }}d\sum _{i=1}^{b^{\prime }}[\gcd (i,b^{\prime })=d]=\sum _{d\mid b^{\prime }}d\sum _{i=1}^{\frac{b^{\prime }}{d}}[\gcd (i,\frac{b^{\prime }}{d})=1]=\sum _{d\mid b^{\prime }}d\phi (\frac{b^{\prime }}{d})=\sum _{d\mid b^{\prime }}\phi (d)\frac{b^{\prime }}{d}$

显然 $f(x)=\sum _{d\mid x}\phi (d)\frac{x}{d}$ 可以 $O(\sqrt{x})$ 求出单点值。

最终答案为 $=\frac{mn}{4b^2}\cdot \left(ab\left(m+1\right)\left(n+1\right)-2b^2+2g^{2}f(\frac{b}{g})\right)$

总的时间复杂度为 $O(T\sqrt{b})$

例题3

定义 $f(n)=\sum _{i=1}^n\lfloor \frac{n}{i}\rfloor$，特殊的，$f(0)=0$

给出 $m$，你需要给出长度为 $n$ 的自然数数列，使 $\sum _{i=1}^n(f(a_i+1)-f(a_i))=m$

采用 $\text{SPJ}$ 评测。

$1\le n\le 20，0\le a_i<2^{63},1\le m\le 2\times 10^5$

---

这题不用什么技巧，直接爆算。

$\begin{array}{rl}f(n+1)-f(n)& =\sum _{i=1}^{n+1}\lfloor \frac{n+1}{i}\rfloor -\sum _{i=1}^n\lfloor \frac{n}{i}\rfloor \\ & =1+\sum _{i=1}^n\left(\lfloor \frac{n+1}{i}\rfloor -\lfloor \frac{n}{i}\rfloor \right)\\ & =\sum _{i=1}^{n+1}\frac{1+n\%i-(n+1)\%i}{i}\end{array}$

显然当 $i$ 是 $n+1$ 的因数时，$1+n\%i-(n+1)\%i$ 等于 $1$，否则为 $0$。

即 $f(n+1)-f(n)={\sigma }_0(n+1)$

观察到 $1\le n\le 20,1\le m\le 2\times 10^5$,容易想到构造出一些 $n$ 满足 $f(n+1)-f(n)=2^0,2^1,\dots ,2^{17}$

我们都知道 ${\sigma }_0(n)=\prod _{i=1}^m(c_i+1)$，其中 $n=p_1^{c_1}{p}_2^{c_2}\dots p_m^{c_m}$

只需令 $n$ 为前几个质数的乘积，即可构造出 ${\sigma }_0(n)$ 为 $2$ 的幂。

注意 $n$ 要在 $\text{long long}$ 范围内，而 $2\times 3\times 5\times \cdots \times 47$（共 $15$ 个质数）已经是极限，所以可以放弃后面的大质数，给前面的 $2,3$ 加次数。这样可以构造出 $2^{16},2^{17}$。

类欧几里得

这三个式子 $$\sum _{i=0}^n\lfloor \frac{ai+b}{c}\rfloor ,\sum _{i=0}^n{\lfloor \frac{ai+b}{c}\rfloor }^2,\sum _{i=0}^{n}i\lfloor \frac{ai+b}{c}\rfloor$$

都可以用类欧几里得求。时间复杂度均为 $O(\sqrt{n})$。（分母为常数，分子是一次形式）

例题4

CF1182F 改编

给出整数 $l,r$ 和奇数 $a,k$，求当 $\underset{x\in [l,r]\cap \mathbb{Z}}{\min }\tan \left(\frac{a}{k}\pi x\right)$ 取得最小值时的最小整数 $x$。

题解参考 CF1182F

进制转换

形如 $\lfloor \frac{A}{a^b}\rfloor$，分母中有指数，$a^b$ 又特别大，可以考虑使用 $\text{FFT}$。

$\lfloor \frac{A}{a^b}\rfloor =\frac{A-A\%a^b}{a^b}$

联想到一个数 $n$ 模 $2^x$ 相当于把 $n$ 转换为二进制后取后面的 $x$ 位。

所以求 $A\%a^b$ 可以先把 $A$ 转成 $a$ 进制再进行运算。有时会有奇效。

例题5

from DengDuck
求 $\lfloor \frac{a^b}{c^d}\rfloor$

$1\le a,b\le 10^9,1\le c\le 100,1\le d\le 10^4$
答案模 $998244353$

---

将 $a$ 转成 $c$ 进制，然后将各位系数看作是一个多项式，然后做快速幂。其中多项式乘法用 $FFT$ 快速算出。

时间复杂度 $O(d\log d\log b)$