数论分块
引理
\[\lfloor\frac{a}{bc}\rfloor=\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor \]数论分块
对于 \(\displaystyle h(i)=\lfloor\frac{n}{i}\rfloor\) ，设 \(f(l)=x\)。
则 \(\displaystyle\forall i\in [l, \lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor]\)，\(h(i)=x\)。
P2261 [CQOI2007] 余数求和
给定 \(n,k\)，求
\[\sum_{i=1}^{n} k\bmod i \]不难发现 \(\displaystyle k\bmod i=k-i\lfloor\frac{k}{i}\rfloor\)。于是数论分块即可，时间复杂度 \(\Theta(\sqrt n)\)。
P3935 Calculating
设 \(x\) 分解质因数后结果为 \(\prod_{i=1}^{n} p_i^{k_i}\)，定义 \(f(x)=\prod_{i=1}^{n} (k_i+1)\)，求
\[\sum_{i=l}^{r} f(i) \]\(f\) 函数实际上求了 \(x\) 的因数个数。
对于正整数 \(n\) 和 \(p\)，\([1,n]\) 内能被 \(p\) 整除的数仅有 \(\lfloor\frac{n}{p}\rfloor\) 个。
（证明：仅有形如 \(1p,2p,\cdots, kp\) 这样的数能被整除。而 \(kp\leq n\iff k\leq \lfloor\frac{n}{p}\rfloor\)。）
然后利用一点前缀和与差分的知识，我们不难得到区间 \([l,r]\) 内能被 \(p\) 整除的数仅有 \(\left(\lfloor\frac{r}{p}\rfloor-\lfloor\frac{l-1}{p}\rfloor\right)\) 个。
那么我们枚举这个 \(p\) 直接算就好了。即
\[\sum_{i=1}^{r} \left\{\lfloor\frac{r}{i}\rfloor-\lfloor\frac{l-1}{i}\rfloor\right\} \]时间复杂度 \(\Theta(\sqrt n)\)。
P2260 [清华集训2012] 模积和
求
\[\sum_{i=1}^{n} \sum_{j=1}^{m} (n \bmod i) \times (m \bmod j), i \neq j \]\(\bmod 19940417\) 后的结果。
不妨设 \(n\leq m\)。
首先可以把不相关的部分提出来。对于 \(i\neq j\) 的限制，我们最后减去 \(\sum (n\bmod i)(m\bmod i)\) 即可。
\[\sum_{i=1}^{n} (n\bmod i)\times \sum_{j=1}^{m} (m\bmod j) \]然后拆开。
\[\sum_{i=1}^n \left(n-i\lfloor\frac{n}{i}\rfloor\right)\times \sum_{j=1}^m \left(m-j\lfloor\frac{m}{j}\rfloor\right) \]然后就是
\[\left(n^2-\sum_{i=1}^n i\lfloor\frac{n}{i}\rfloor\right)\left(m^2-\sum_{i=1}^m i\lfloor\frac{m}{i}\rfloor\right) \]对于减掉的式子，我们有
\[\begin{aligned} \sum (n\bmod i)(m\bmod i)&=\sum_{i=1}^{n} (n-i\lfloor\frac{n}{i}\rfloor)(m-i\lfloor\frac{m}{i}\rfloor) \\ &=\sum_{i=1}^{n} (nm-mi\lfloor\frac{n}{i}\rfloor-ni\frac{m}{i}+i^2\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor) \end{aligned} \]可能要用到的公式：
\[\sum_{i=1}^{n} i^2=\frac{n(n+1)(2n+1)}{6} \]注意，\(19940417\) 不是素数。
积性函数
对于算术函数 \(f\)，若对于 \(p\perp q\)，有 \(f(pq)=f(p)f(q)\) 恒成立，则称 \(f\) 为积性的。
若 \(\forall p,q\)，有 \(f(pq)=f(p)f(q)\) 成立，我们称 \(f\) 为完全积性的。
对于任意积性函数 \(f\)，都有 \(f(1)=1\)。
| \(f\) | 描述 | 公式 | 积性 |
|---|---|---|---|
| \(\varepsilon\) | 元函数 | \(\varepsilon\ast f=f\)，\(\mu\ast 1=\varepsilon\) | 完全 |
| \(1\) | 常值 \(1\) 函数 | - | 完全 |
| \(\operatorname{Id}\) | 恒等函数 | \(\varphi\ast \operatorname{Id}=\operatorname{Id}\) | 完全 |
| \(\mu\) | Mobius 函数 | \(f=\mu \ast g\iff g=f\ast 1\) | 积性 |
| \(\varphi\) | Euler 函数 | \(\mu\ast \operatorname{Id}=\varphi\) | 积性 |
| \(\sigma_0\) | 因数个数函数 | \(1\ast 1=\sigma_0\) | 积性 |
| \(\sigma_1\) | 因数和函数 | \(\operatorname{Id}\ast 1=\sigma_1\) | 积性 |
Mobius 反演
对于积性函数 \(f,g\)，
\[f=\mu\ast g\iff g=f\ast 1 \]证明：
由定义有 \(f(n)=\sum_{d\mid n}\mu(d)g(\frac{n}{d})\)
\[\begin{aligned} f\ast 1&=\sum_{d\mid n} f(d) \\ &=\sum_{d\mid n} \sum_{d'\mid d} \mu(d') g(\frac{d}{d'}) \\ &=\sum_{d'\mid n} \sum_{d'\mid d} \mu(\frac{d}{d'}) g(d') \\ &=\sum_{d'\mid n}g(d') \sum_{d'\mid d} \mu(\frac{d}{d'}) \\ &=\sum_{d'\mid n}g(d') \sum_{k\mid \frac{n}{d'}} \mu(\frac{kd'}{d'}) \\ \end{aligned} \]当且仅当 \(\frac{n}{d'}=1\) 即 \(d'=n\) 时，\(\mu\) 有非 \(0\) 值 \(1\)。
于是 \(f\ast 1=g\)。证毕。
- 形式 1
- 形式 2
常见应用
以下默认 \(n\leq m\)。
- 形式 1
利用数论分块，时间复杂度 \(\Theta(\sqrt n)\)。
- 形式 2
- 形式 3
令 \(t=kd\)。于是
\[\begin{aligned} &=\sum_{t=1}^{n}\sum_{d\mid t}f(d)\mu\left(\frac{t}{d}\right) \lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor\\ &=\sum_{t=1}^{n} \lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor\sum_{d=1}^{n} f(d)\mu\left(\frac{t}{d}\right) \end{aligned} \]预处理后时间复杂度 \(\Theta(n)\sim \Theta(n)\)。
PGCD - Primes in GCD Table
求
\[\sum_{p\in \mathbb{P}}\sum_{i=1}^{n}\sum_{j=1}^{m} [\gcd(i,j)=p] \]\[\begin{aligned} \sum_{p\in \mathbb{P}}\sum_{i=1}^{n}\sum_{j=1}^{m} [\gcd(i,j)=p]&=\sum_{p\in \mathbb{P}}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor} [\gcd(i,j)=1] \\ &=\sum_{p\in \mathbb{P}}\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor} \mu(d)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor \\ \end{aligned} \]做到这一步已经是 \(\displaystyle \Theta(T\frac{n}{\ln n})\) 的了。不过我们还可以更进一步。
设 \(t=pd\)，则原式等价于
\[\sum_{t=1}^{n}\lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor\sum_{p\mid t, p\in \mathbb{P}}\mu(\frac{t}{p}) \]设 \(f(t)=\sum_{p\mid t, p\in \mathbb{P}} \mu(\frac{t}{p})\)。如果能快速预处理出 \(f\) 就可以在 \(\Theta(T\sqrt n)\) 内解决本题。
一方面可以枚举所有素数的倍数来预处理。这样是 \(\Theta(n\log \log n)\) 的。
下面我们进行分讨。以下设 \(x\) 的最小素因子为 \(y\)，且 \(x=iy\)。
- \(x\in \mathbb{P}\) 或 \(x=1\)
显然有 \(f(x)=1\)。
- \(i\bmod y=0\)
\(\sum_{p\mid iy} \mu(\frac{iy}{p})\) 当且仅当 \(p=y\) 时可能不为 \(0\)。那么有 \(f(x)=\mu(i)\)。
- \(i\bmod y\neq 0\)
我们有 \(f(\frac{iy}{p})=-f(\frac{i}{p})\)，因此 \(f(i)\) 中的每一项都在 \(f(x)\) 中有对应项。当 \(p=y\) 时，\(\mu(i)\) 会有额外的贡献（因为多了素因子 \(y\)）。于是 \(f(x)=\mu(i)-f(i)\)。
综上
\[f(x)=\begin{cases} 1 & x\in \mathbb{P} \\ \mu(i) & i\bmod y=0 \\ -f(i)+\mu(i) & i\bmod i\neq 0 \end{cases} \]时间复杂度 \(\Theta(n\log \log n)\sim \Theta(\sqrt n)\) 或 \(\Theta(n)\sim \Theta(\sqrt n)\)。
GCDMAT - GCD OF MATRIX
求
\[\sum_{i=i_1}^{i_2}\sum_{j=j_1}^{j_2} \gcd(i,j) \]直接拆成四个询问，套用形式 2 即可。\(\Theta(T\sqrt n)\)。
P3327 [SDOI2015] 约数个数和
记 \(d(x)\) 为 \(x\) 的约数个数，给定 \(n,m\)，求
\[\sum_{i=1}^n\sum_{j=1}^md(ij) \]我们知道
\[d(n)=\sum_{d\mid n} 1 \]我们有 \(d(n)\) 的特殊性质
\[d(ij)=\sum_{x\mid i}\sum_{y\mid j} [\gcd(x,y)=1] \]则有
\[\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^m\sum_{x\mid i}\sum_{y\mid j} [\gcd(x,y)=1]&=\sum_{x=1}^{n}\sum_{y=1}^{m}\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{y}\rfloor} [\gcd(x,y)=1] \\ &=\sum_{x=1}^{n}\sum_{y=1}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor [\gcd(x,y)=1] \\ &=\sum_{d=1}^{n}\mu(d)\sum_{x=1}^{n} \lfloor\frac{n}{x}\rfloor \sum_{y=1}^{m} \lfloor\frac{m}{y}\rfloor \end{aligned} \]时间复杂度 \(\Theta(n+T\sqrt{n})\)。
P5221 Product
求
\[\prod_{i=1}^n\prod_{j=1}^n\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)} \]对 \(104,857,601\) 取模。
\(200 \texttt{ms},7.81\texttt{MB}\)。\(n\leq 10^6\)。
[RC-02] GCD
求
\[\sum_{i=1}^n\sum_{j=1}^n\sum_{p=1}^{\lfloor\frac{n}{j}\rfloor}\sum_{q=1}^{\lfloor\frac{n}{j}\rfloor}[\gcd(i,j)=1][\gcd(p,q)=1] \]其中 \(n\leq 2\times 10^9\)。
\[\sum_{i=1}^n\sum_{j=1}^n\sum_{p=1}^{\lfloor\frac{n}{j}\rfloor}\sum_{q=1}^{\lfloor\frac{n}{j}\rfloor}[\gcd(i,j)=1][\gcd(p,q)=1] \\ \begin{aligned} &=\sum_{i=1}^n\sum_{j=1}^n\sum_{p=1}^{n}\sum_{q=1}^{n}[\gcd(i,j)=1][\gcd(p,q)=j] \\ &=\sum_{i=1}^n\sum_{p=1}^{n}\sum_{q=1}^{n}[\gcd(i,p,q)=1] \\ &=\sum_{d=1}^{n} \mu(d)\lfloor\frac{n}{d}\rfloor^3 \end{aligned} \]使用杜教筛维护，时间复杂度 \(\Theta(n^{\frac{2}{3}})\)。
P3768 简单的数学题
求
\[\sum_{i=1}^n\sum_{j=1}^n ij \gcd(i,j) \]\(n\leq 10^{10}\)。
\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^n ij \gcd(i,j)&= \sum_{i=1}^n \sum_{j=1}^n ij \sum_{d\mid i,d\mid j} \varphi(d) \\ &=\sum_{d=1}^{n}\varphi(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}(id)(jd)\\ &=\frac{1}{4}\sum_{d=1}^{n}\varphi(d) d^2 \left\{\lfloor\frac{n}{d}\rfloor\left(\lfloor\frac{n}{d}\rfloor+1\right) \right\}^2\\ &=\frac{1}{4}\sum_{d=1}^{n}\varphi(d) d^2\left(\lfloor\frac{n}{d}\rfloor^2+\lfloor\frac{n}{d}\rfloor\right)^2 \end{aligned} \]使用杜教筛维护。时间复杂度 \(\Theta(n^{\frac{2}{3}})\)。
P3172 [CQOI2015] 选数
求
\[\sum_{i_1=l}^{r}\sum_{i_2=l}^r\cdots\sum_{i_n=l}^r [\gcd(i_1,i_2,\cdots,i_n)=k] \]\(r-l\leq 10^5\)，\(n,k\leq 10^9\)。
不妨先计算出 \(i\in [1,r]\) 的答案再减去 \(i\in [1,l-1]\) 的答案。以下令 \(\displaystyle n:=\lfloor\frac{r}{k}\rfloor\)。
\[\sum_{i_1=1}^{r}\sum_{i_2=1}^r\cdots\sum_{i_n=1}^r [\gcd(i_1,i_2,\cdots,i_n)=k] \\ \begin{aligned} &=\sum_{i_1=1}^{n}\sum_{i_2=1}^{n}\cdots\sum_{i_n=1}^{n} [\gcd(i_1,i_2,\cdots,i_n)=1] \\ &=\sum_{i_1=1}^{n}\sum_{i_2=1}^{n}\cdots\sum_{i_n=1}^{n}\sum_{d\mid i_1,d\mid i_2,\cdots, d\mid i_n} \mu(d) \\ &=\sum_{d=1}^{n}\mu(d)\sum_{i_1=1}^{n}\sum_{i_2=1}^{n}\cdots\sum_{i_n=1}^{n}[d\mid i_1][d\mid i_2]\cdots[d\mid i_n] \\ &=\sum_{d=1}^{n}\mu(d)\lfloor\frac{n}{d}\rfloor^n \end{aligned} \]
对于 \([1,l-1]\) 的计算同理。时间复杂度 \(\Theta(n^{\frac{2}{3}}\log n)\)。
以上是错误的解法。正确的解法：令 \(L=\lceil\frac{l}{k}\rceil\)，\(R=\lfloor\frac{r}{k}\rfloor\)。于是有
\[\sum_{i_1=l}^{r}\sum_{i_2=l}^r\cdots\sum_{i_n=l}^r [\gcd(i_1,i_2,\cdots,i_n)=k] \\ \begin{aligned} &=\sum_{i_1=L}^{R}\sum_{i_2=L}^{R}\cdots\sum_{i_n=L}^{R} [\gcd(i_1,i_2,\cdots,i_n)=1] \\ &=\sum_{i_1=L}^{R}\sum_{i_2=L}^{R}\cdots\sum_{i_n=L}^{R}\sum_{d\mid i_1,d\mid i_2,\cdots, d\mid i_n} \mu(d) \\ &=\sum_{d=1}^{R}\mu(d)\sum_{i_1=L}^{R}\sum_{i_2=L}^{R}\cdots\sum_{i_n=L}^{R}[d\mid i_1][d\mid i_2]\cdots[d\mid i_n] \\ &=\sum_{d=1}^{R}\mu(d)\left(\lfloor\frac{R}{d}\rfloor-\lfloor\frac{L-1}{d}\rfloor\right)^n \end{aligned} \]可以用杜教筛维护。
P4449 于神之怒加强版
求
\[\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^k \]设 \(n\leq m\)。
不难想到
\[\begin{aligned} \sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^k&=\sum_{i=1}^n\sum_{j=1}^{m}\sum_{d\mid i,d\mid j}d^k[d=\gcd(i,j)] \\ &=\sum_{i=1}^n\sum_{j=1}^{m}\sum_{d\mid i,d\mid j}d^k[d=\gcd(i,j)] \\ &=\sum_{d=1}^n d^k\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=d] \\ &=\sum_{d=1}^n d^k \sum_{p=1}^{\lfloor\frac{n}{d}\rfloor} \mu(p)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor \end{aligned} \]不妨设 \(t=pd\)。
\[\begin{aligned} &=\sum_{t=1}^{n}\lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor\sum_{d\mid t} \mu\left(\frac{t}{d}\right)d^k \end{aligned} \]不妨设 \(f(n)=\sum_{d\mid n} \mu(\frac{n}{d})d^k\)。考虑快速求出 \(f\)。
以下设 \(y\) 为 \(x\) 的最小素因子，且 \(x=iy\)。
- \(f=1\) 或 \(f\in \mathbb{P}\)
显然有 \(f(x)=x^k\)。
- \(i\bmod y=0\)
\(f(x)=f(i)\)。
- \(i\bmod y\neq 0\)
\(f(x)=f(y)-f(i)\)。
P6825 「EZEC-4」求和
求
\[\displaystyle\sum_{i = 1}^n \sum_{j = 1}^n \gcd(i,j)^{i + j} \]不妨令 \(\displaystyle N:=\lfloor\frac{n}{d}\rfloor\)
以下是错解。
\[ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^n \gcd(i,j)^{i+j}&=\sum_{d=1}^n \mu(d)\sum_{i=1}^n\sum_{j=1}^n [d\mid i][d\mid j]d^id^j \\ &=\sum_{d=1}^n \mu(d)\sum_{i=1}^{N}\sum_{j=1}^{N} d^{id} d^{jd} \\ &=\sum_{d=1}^n \mu(d) \left(\frac{d^{(N+1)d}-d^d}{d^d-1}\right)^2 \end{aligned} \]\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^n \gcd(i,j)^{i+j}&=\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n d^{i+j}[\gcd(i,j)=d] \\ &=\sum_{d=1}^n\sum_{i=1}^N\sum_{j=1}^N d^{(i+j)d}[\gcd(i,j)=1] \\ &=\sum_{d=1}^n\sum_{i=1}^{N}\sum_{j=1}^N d^{(i+j)d}\sum_{p\mid i,p\mid j} \mu(p) \\ &=\sum_{d=1}^n\sum_{p=1}^{N} \mu(p) \sum_{i=1}^N\sum_{j=1}^N d^{(i+j)d} \\ &=\sum_{d=1}^n\sum_{p=1}^{N} \mu(p) \sum_{i=1}^{\lfloor\frac{N}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{N}{p}\rfloor} d^{(i+j)dp} \end{aligned} \]
let \(t=dp\)。
\[\begin{aligned} &=\sum_{d=1}^n\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor} \mu(p) \sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{t}\rfloor} d^{(i+j)t} \\ &=\sum_{d=1}^n\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor} \mu(p) \left[\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor} (d^{t})^{i}\right]^2 \end{aligned} \]后一部分是 \(\Theta(\log n)\) 的等比数列求和。前面是 \(\Theta(n\log n)\) 的调和级数。
可以证明是 \(\Theta(n\log n)\) 的。你要说是 \(\mathcal{O}(n^{114})\) 也没错。
P1829 [国家集训队] Crash的数字表格 / JZPTAB
求
\[\sum_{i=1}^n \sum_{j=1}^m \operatorname{lcm}(i,j) \]记 \(s(x)=\frac{1}{2}x(x+1)\)。
\[\begin{aligned} \sum_{i=1}^n \sum_{j=1}^m \operatorname{lcm}(i,j) &= \sum_{i=1}^n \sum_{j=1}^m \frac{ij}{\gcd(i,j)} \\ &=\sum_{i=1}^n \sum_{j=1}^m ij \sum_{d=1}^n [d=\gcd(i,j)]\frac{1}{d} \\ &=\sum_{d=1}^n \sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor} ijd [\gcd(i,j) =1] \\ &=\sum_{d=1}^n d\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor} ij \sum_{k\mid i,k\mid j} \mu(k) \\ &=\sum_{d=1}^n d\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)k^2\sum_{i=1}^{\lfloor \frac{n}{kd}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor} ij \\ &=\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor} \mu(k)k^2\cdot s(\lfloor\frac{n}{kd}\rfloor) s(\lfloor\frac{m}{kd}\rfloor) \end{aligned} \]let \(t=kd\)，有
\[\begin{aligned} &=\sum_{t=1}^{n}s(\lfloor\frac{n}{t}\rfloor)s(\lfloor\frac{m}{t}\rfloor)\sum_{d\mid t} d \mu(\frac{t}{d})\cdot (\frac{t}{d})^2 \\ &=\sum_{t=1}^{n}t\cdot s(\lfloor\frac{n}{t}\rfloor)s(\lfloor\frac{m}{t}\rfloor) \sum_{d\mid t}\mu(\frac{t}{d})\cdot (\frac{t}{d}) \end{aligned} \]考虑 \(\mu\ast \operatorname{Id}\) 的求法。
当 \(n=1\) 时，显然为 \(1\)。
当 \(n\in \mathbb{P}\) 时，显然有 \(f(n)=1-p\)。
当 \(i\bmod y=0\) 时，显然有 \(f(n)=f(i)\)。
否则 \(f(n)=f(i)f(y)\)。然后就做完了。
P6156 简单题
求
\[\sum_{i=1}^n\sum_{j=1}^n(i+j)^kf(\gcd(i,j))\gcd(i,j) \]其中 \(f(n)=[\forall p\in \mathbb{P}, p^2\nmid n]\)
\[\sum_{i=1}^n\sum_{j=1}^n(i+j)^kf(\gcd(i,j))\gcd(i,j) \\ \begin{aligned} &=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k \sum_{d\mid i,d\mid j} [d=\gcd(i,j)] d\cdot f(d) \\ &=\sum_{d=1}^n d^{k+1}\cdot f(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}(i+j)^k[\gcd(i,j)=1] \\ &=\sum_{d=1}^n d^{k+1}\cdot f(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}(i+j)^k\sum_{p\mid i,p\mid j} \mu(p) \\ &=\sum_{d=1}^{n} d^{k+1}\cdot f(d)\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)p^k\sum_{i=1}^{\lfloor\frac{n}{pd}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{pd}\rfloor} (i+j)^k \end{aligned} \]let \(s(n)=\sum_{i=1}^n\sum_{j=1}^n (i+j)^k\)，\(t=pd\)，此外不难发现 \(f(n)=\mu(n)^2\)。
不难发现
\[\begin{aligned} &=\sum_{d=1}^{n} d^{k+1}\cdot \mu(d)^2\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)p^k\cdot s(\lfloor\frac{n}{pd}\rfloor) \\ &=\sum_{t=1}^{n} s(\lfloor\frac{n}{t}\rfloor)\sum_{d\mid t} d^{k+1}\cdot \mu(d)^2 \cdot \mu(\frac{t}{d})\cdot (\frac{t}{d})^k \\ &=\sum_{t=1}^{n} s(\lfloor\frac{n}{t}\rfloor)\sum_{d\mid t} d\cdot \mu(d)^2 \cdot \mu(\frac{t}{d})\cdot t^k \end{aligned} \]考虑令 \(g(n)=\sum_{d\mid n} d\cdot \mu(d)^2 \cdot \mu(\frac{n}{d})\cdot n^k\)。不难证明其为积性函数。
对于 \(s(n)\)，令 \(p(n)=\sum_{i=1}^n i^k\)，\(q(n)=\sum_{i=1}^n p(n)\)，不难观察到
\[s(n)=\sum_{i=1}^{n} \left[p(n+i)-p(i)\right]=q(2n)-2q(n) \]然后就做完了。
GCDMAT2 - GCD OF MATRIX (hard)
求
\[\sum_{i=i1}^{i2}\sum_{j=j1}^{j2}\gcd(i,j) \]数据组数 \(T\leq 5\times 10^4\)，\(i_2,j_2\leq 10^6\)。
P7486 「Stoi2031」彩虹
求
\[\prod_{i=l}^{r}\prod_{j=l}^{r} \operatorname{lcm}(i,j)^{\operatorname{lcm}(i,j)} \bmod 32465177 \]化式子。我们只需要考虑 \(\prod_{i=1}^{n}\prod_{j=1}^m\) 的情况，理由显然。
\[\begin{aligned} \prod_{i=1}^{n}\prod_{j=1}^{m} \operatorname{lcm}(i,j)^{\operatorname{lcm}(i,j)}&=\prod_{d=1}^{n}\prod_{i=1}^{\lfloor\frac{n}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{d}\rfloor} (ijd)^{ijd[d=\gcd(i,j)]} \\ &=\prod_{d=1}^{n}\prod_{p=1}^{\lfloor\frac{n}{d}\rfloor}\prod_{i=1}^{\lfloor\frac{n}{pd}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{pd}\rfloor} (ijdp^2)^{ijdp^2\mu(p)} \end{aligned} \]不妨记 \(\displaystyle s(n)=\frac{n(n+1)}{2}\)。
我们有
\[\prod_{i=1}^{n}\prod_{j=1}^{m}(ij)^{ij} =\prod_{i=1}^{n}\prod_{j=1}^{m} (i^i)^j(j^j)^i \\ =\left[\prod_{i=1}^n i^i\right]^{s(m)}\left[\prod_{i=1}^m i^i\right]^{s(n)}\]记为 \(F(n,m)\)。
而且我们有
\[\prod_{i=1}^{n}\prod_{j=1}^{m} t^{ij}=t^{s(n)s(m)} \]则
\[\begin{aligned} &=\prod_{d=1}^{n}\prod_{p=1}^{\lfloor\frac{n}{d}\rfloor}\prod_{i=1}^{\lfloor\frac{n}{pd}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{pd}\rfloor} (ijdp^2)^{ijdp^2\mu(p)} \\ &=\prod_{d=1}^{n}\prod_{p=1}^{\lfloor\frac{n}{d}\rfloor}\left[\prod_{i=1}^{\lfloor\frac{n}{pd}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{pd}\rfloor} (ij)^{ij}\cdot (dp^2)^{ij} \right]^{dp^2\mu(p)}\\ &=\prod_{d=1}^{n}\prod_{p=1}^{\lfloor\frac{n}{d}\rfloor} \left[F\left(\lfloor\frac{n}{pd}\rfloor,\lfloor\frac{m}{pd}\rfloor\right)\cdot (dp^2)^{s(\lfloor\frac{n}{pd}\rfloor)s(\lfloor\frac{m}{pd}\rfloor)}\right]^{dp^2\mu(p)} \end{aligned} \]不妨令 \(dp=t\)。记 \(g(n)=\sum_{d\mid n} d\mu(d)\)，\(h(n)=\prod_{d\mid n} d^{d\mu(d)}\)。
我们得到
\[\begin{aligned} &=\prod_{t=1}^{n}\prod_{p\mid t} \left[F\left(\lfloor\frac{n}{t}\rfloor,\lfloor\frac{m}{t}\rfloor\right)\cdot (tp)^{s(\lfloor\frac{n}{t}\rfloor)s(\lfloor\frac{m}{t}\rfloor)}\right]^{tp\mu(p)} \\ &=\prod_{t=1}^{n} \left[\left[F(\lfloor\frac{n}{t}\rfloor,\lfloor\frac{m}{t}\rfloor)\cdot t^{s(\lfloor\frac{n}{t}\rfloor)s(\lfloor\frac{m}{t}\rfloor)}\right]^{{\sum_{p\mid t} p\mu(p)} } \left(\prod_{p\mid t} p^{p\mu(p)}\right)^{s(\lfloor\frac{n}{t}\rfloor)s(\lfloor\frac{m}{t}\rfloor)} \right]^t \\ &=\prod_{t=1}^{n} \left[\left[F(\lfloor\frac{n}{t}\rfloor,\lfloor\frac{m}{t}\rfloor)\cdot t^{s(\lfloor\frac{n}{t}\rfloor)s(\lfloor\frac{m}{t}\rfloor)}\right]^{{g(t)} } h(t)^{s(\lfloor\frac{n}{t}\rfloor)s(\lfloor\frac{m}{t}\rfloor)} \right]^t \\ &=\prod_{y=1}^{n} F(\lfloor\frac{n}{t}\rfloor,\lfloor\frac{m}{t}\rfloor)^{tg(t)}\cdot \left[t^{g(t)}h(t)\right]^{t\cdot s(\lfloor\frac{n}{t}\rfloor)s(\lfloor\frac{m}{t}\rfloor)} \end{aligned} \]再令 \(G(t)=t\cdot g(t)\)，\(H(t)=\left[t^{g(t)}\cdot h(t)\right]^{t}\)。于是
\[=\prod_{y=1}^{n} F(\lfloor\frac{n}{t}\rfloor,\lfloor\frac{m}{t}\rfloor)^{G(t)}\cdot H(t)^{s(\lfloor\frac{n}{t}\rfloor)s(\lfloor\frac{m}{t}\rfloor)}\]讨论一下乘法的数论分块。
设极长的区间为 \([l,r]\)，则对答案的贡献为
\[F(\lfloor\frac{n}{l}\rfloor,\lfloor\frac{m}{l}\rfloor)^{sum_G(r)-sum_G(l-1)}\cdot \left[\frac{mul_H(r)}{mul_H(l-1)}\right]^{s(\lfloor\frac{n}{t}\rfloor)s(\lfloor\frac{m}{t}\rfloor)} \]然后我们需要预处理出 \(F,G,H\)。然后《就》做完了。
回顾一下 \(F(n,m),G(n),H(n)\) 的定义。
\[F(n,m)=\left[\prod_{i=1}^n i^i\right]^{s(m)}\left[\prod_{i=1}^m i^i\right]^{s(n)} \]实际上只需要预处理 \(f(n)=\prod_{i=1}^{n} i^i\)，那么 \(F(n,m)=f(n)^{s(m)}f(m)^{s(n)}\)
\[G(n)=n\sum_{d\mid n} d\mu(d) \]\[H(n)=\left[n^{g(n)}\cdot h(n)\right]^n \]对于 \(g(n)\) 和 \(h(n)\)，我们可以通过枚举倍数在 \(\Theta(n\ln n)\) 的时间内预处理出。于是 \(G\) 和 \(H\) 是好求的。
于是我们在 \(\Theta(\sqrt n\log n+n\log n)\) 的时间内解决了本题。
现在是 16:46，我看我什么时候写完。
Update：2.7 13:15 AC 了此题。
注意什么时候对 \(p\) 取模，什么时候对 \((p-1)\) 取模。
P3704 数字表格
求
\[\prod_{i=1}^{n}\prod_{j=1}^{m} f(\gcd(i,j)) \]其中 \(f(i)\) 代表 Fibonacci 数列的第 \(i\) 项。
简单反演一下。
\[\begin{aligned} \prod_{i=1}^{n}\prod_{j=1}^{m} f(\gcd(i,j))&=\prod_{i=1}^{n}\prod_{j=1}^{m}\prod_{d\mid i,d\mid j} f(d)^{[d=\gcd(i,j)]} \\ &=\prod_{d=1}^{n}\prod_{j=1}^{\lfloor\frac{n}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{d}\rfloor} f(d)^{[\gcd(i,j)=1]} \\ &=\prod_{d=1}^{n}\prod_{p=1}^{\lfloor\frac{n}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{n}{pd}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{pd}\rfloor} f(d)^{\mu(p)} \\ &=\prod_{t=1}^{n}\left[\prod_{d\mid p} f(d)^{\mu(\frac{t}{d})}\right]^{s(\lfloor\frac{n}{t}\rfloor)s(\lfloor\frac{m}{t}\rfloor)} \end{aligned} \]时间复杂度 \(\Theta(T\sqrt n\log p+n\ln n\log p)\)。
P3312 [SDOI2014] 数表
P6271 [湖北省队互测2014] 一个人的数论
好题。
此处的 \(k\) 与题目中的 \(d\) 相同。
记 \(f_k(n)\) 为所有小于 \(n\) 且与 \(n\) 互素的正整数的 \(d\) 次方和，求
\[f_k(n) \bmod 10^9+7 \]给定 \(n\) 的素因数分解式。记 \(w\) 为素因数个数，\(a_i\) 为因数次数。\(k\leq 10^2\)，\(w \leq 10^3\)，\(p_i \leq 10^9\)，\(a_i \leq 10^9\)。
即为 \(\sum_{i=1}^n[\gcd(i,n)=1] i^k\)。不妨记 \(s_k(n)=\sum_{i=1}^n i^k=\sum_{i=0}^{k+1}a_in^i\)。
\[\begin{aligned} \sum_{i=1}^n[\gcd(i,n)=1] i^k&=\sum_{i=1}^n i^k\sum_{d\mid i,d\mid n} \mu(d) \\ &=\sum_{d\mid n} \mu(d) \sum_{j=1}^{\frac{n}{d}} (jd)^k \\ &=\sum_{d\mid n} \mu(d)d^k s_k(\frac{n}{d}) \\ &=\sum_{d\mid n} \mu(d) d^k \sum_{i=0}^{k+1} a_i(\frac{n}{d})^i \\ &=\sum_{d\mid n} \mu(d) d^k \sum_{i=0}^{k+1} a_i n^i d^{-i} \\ &=\sum_{i=0}^{k+1}a_in^i \sum_{d\mid n}\mu(d)d^{k-i} \end{aligned} \]显然 \(\mu(d)d^{k-i}\) 是一个积性函数。于是有
\[\begin{aligned} &=\sum_{i=0}^{k+1}a_in^i \prod_{j=1}^{w}\sum_{l=0}^{a_j} \mu(p_j^l)p_j^{l(k-i)} \end{aligned} \]注意到当且仅当 \(l\leq 1\) 时，\(\mu(p_j^l)p_j^{l(k-i)}\neq 0\)。于是不难化为
\[\begin{aligned} &=\sum_{i=0}^{k+1}a_in^i \prod_{j=1}^{w} (1-p_j^{k-i}) \end{aligned} \]系数 \(a_i\) 可以暴力算出，是 \(\Theta(k^3)\) 的。
总时间复杂度 \(\Theta(k^3+kw)\)。
P6810 「MCOI-02」Convex Hull 凸包
求
\[\displaystyle\sum_{i = 1}^n \sum_{j = 1}^m \sigma_0(i) \sigma_0(j) \sigma_0(\gcd(i, j)) \]\(n,m\leq 2\times 10^6\)。
\(\sigma_0\) 表示因数个数函数。
我们可以简单反演一下
\[\begin{aligned} \sum_{i = 1}^n \sum_{j = 1}^m \sigma_0(i) \sigma_0(j) \sigma_0(\gcd(i, j))&=\sum_{i=1}^n\sum_{j=1}^m \sigma_0(i)\sigma_0(j)\sum_{d\mid i,d\mid j} \sigma_0(d)[d=\gcd(i,j)] \\ &=\sum_{d=1}^n \sigma_0(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor} \sigma_0(id)\sigma_0(jd)[\gcd(i,j)=1] \\ &=\sum_{d=1}^n \sigma_0(d)\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor} \mu(p)\sum_{i=1}^{\lfloor\frac{n}{pd}\rfloor}\sum_{i=1}^{\lfloor\frac{m}{pd}\rfloor} \sigma_0(ipd)\sigma_0(jpd) \\ &=\sum_{t=1}^n \sum_{d\mid t} \sigma_0(d)\mu(\frac{t}{d})\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sigma_0(it)\sum_{j=1}^{\lfloor\frac{m}{t}\rfloor}\sigma_0(jt) \end{aligned} \]然后你会发现中间有个卷积是可以线性调和地算的。然后你还会发现后面也是一个线性调和的枚举。
所以总复杂度 \(\Theta(n\log n)\)。
[AGC038C] LCMs / P3911 最小公倍数之和
给定数列 \(a\)。求
\[\sum_{i=1}^n\sum_{j=1}^n \operatorname{lcm}(a_i,a_j) \]\(n\le 2\times 10^5\)，\(1 \le a_i \le 10^6\)。
不妨记 \(N=10^6\)。
\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^n \operatorname{lcm}(a_i,a_j)&=\sum_{i=1}^n \sum_{j=1}^n \sum_{d\mid a_i,d\mid a_j} [d=\gcd(a_i,a_j)]\frac{a_i\cdot a_j}{d} \\ &=\sum_{d=1}^{N} d\left(\sum_{i=1}^{\lfloor\frac{N}{d}\rfloor} \sum_{j=1}^{\lfloor\frac{N}{d}\rfloor} cnt_{id}cnt_{jd}[\gcd(i,j)=1]i\cdot j \right) \\ &=\sum_{d=1}^N d\sum_{p=1}^{\lfloor\frac{N}{d}\rfloor} p^2\mu(p) \sum_{i=1}^{\lfloor\frac{N}{pd}\rfloor} \sum_{j=1}^{\lfloor\frac{N}{pd}\rfloor} cnt_{ipd}cnt_{jpd}ij \\ &=\sum_{t=1}^{N}t\sum_{p\mid t}p\mu(p) \sum_{i=1}^{\lfloor\frac{N}{t}\rfloor} \sum_{j=1}^{\lfloor\frac{N}{t}\rfloor} cnt_{it}cnt_{jt}ij \end{aligned} \]时间复杂度 \(\Theta(n\log n)\)。
P4240 毒瘤之神的考验
求
\[\sum_{i=1}^n \sum_{j=1}^m \varphi(ij) \]对 \(998,422,353\) 取模。\(n,m\leq 10^5\)，\(T\leq 10^4\)。
我们有
\[\varphi(ij)=\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))} \]代入得到
\[\begin{aligned} \sum_{i=1}^n \sum_{j=1}^m \varphi(ij)&=\sum_{d=1}^n \frac{d}{\varphi(d)}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum_{j=1}^{\lfloor\frac{m}{d}\rfloor} \varphi(id)\varphi(jd)[\gcd(i,j)=1] \\ &=\sum_{d=1}^n \frac{d}{\varphi(d)} \sum_{p=1}^{\lfloor\frac{n}{d}\rfloor} \mu(p) \sum_{i=1}^{\lfloor\frac{n}{pd}\rfloor} \sum_{j=1}^{\lfloor\frac{m}{pd}\rfloor} \varphi(ipd)\varphi(jpd) \\ &=\sum_{t=1}^{n}\sum_{d\mid t}\frac{d}{\varphi(d)}\mu(\frac{t}{d}) \sum_{i=1}^{\lfloor\frac{n}{t}\rfloor} \sum_{j=1}^{\lfloor\frac{m}{t}\rfloor} \varphi(it)\varphi(jt) \end{aligned} \]至此我们已经做到了单次询问 \(\Theta(n\log n)\)。
观察到我们的瓶颈在于求 \(\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor} \varphi(it)\) 上，考虑优化。
我们不妨试着根号平衡一下。对于 \(t\leq B\)，我们预处理。对于 \(t\gt B\)，我们暴力求。
于是两个时间复杂度加起来就是 \(\Theta(\frac{n^2}{B}+nB)\)，不难发现 \(B=\sqrt n\) 时取得平衡。
我们记 \(f(n,t)=\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor} \varphi(it)\)。我们需要对于 \(\forall t\in [1,B], \forall x\in [1,n]\)，求出 \(f(x,t)\)，然后求出 \(s(n,t)=\sum_{i=1}^t f(n,i)\)。这样空间复杂度是 \(\Theta(n\sqrt n)\) 的，可以接受。
这样可以做到 \(\Theta(\sqrt n)\) 单次询问。于是我们在 \(\Theta((n+T)\sqrt n)\) 内解决了本题。
标签：lfloor,frac,乌斯,sum,mid,rfloor,mu,反演,莫比 From： https://www.cnblogs.com/Starrykiller/p/18016231/mobius-inversion