基础莫反，推式子。

「SPOJ 5971」LCMSUM

SPOJ LCMSUM

TT 组数据，每次求：

∑i=1nlcm⁡(i,n)\sum_{i=1}^n \operatorname{lcm}(i,n)

T≤105,n≤106T\le 10^5,n\le 10^6

∑i=1nlcm⁡(i,n)=∑i=1ni×ngcd⁡(i,n)=12(∑i=1n−1i×ngcd⁡(i,n)+∑i=n−11i×ngcd⁡(i,n))+n=12(∑i=1n−1i×ngcd⁡(i,n)+∑i=n−11i×ngcd⁡(n−i,n))+n=12∑i=1nn2gcd⁡(i,n)+n2\begin{aligned} &\sum_{i=1}^n \operatorname{lcm}(i,n)\\ =&\sum_{i=1}^n \frac{i\times n}{\gcd(i,n)}\\ =&\frac{1}{2}\left( \sum_{i=1}^{n-1} \frac{i\times n}{\gcd(i,n)} +\sum_{i=n-1}^{1} \frac{i\times n}{\gcd(i,n)}\right) + n\\ =&\frac{1}{2}\left( \sum_{i=1}^{n-1} \frac{i\times n}{\gcd(i,n)} +\sum_{i=n-1}^{1} \frac{i\times n}{\gcd(n-i,n)}\right)+n \\ =&\frac{1}{2}\sum_{i=1}^{n} \frac{n^2}{\gcd(i,n)} +\frac{n}{2}\\ \end{aligned}

考虑相同的 gcd⁡(i,n)\gcd(i,n) 一起计算，gcd⁡(i,n)=d\gcd(i,n)=d 的 ii 有 φ(nd)\varphi(\frac{n}{d}) 个。

12∑d∣nn2φ(nd)d+n2=n2∑d∣nndφ(nd)+n2=n2(∑d∣nd⋅φ(d))+n2\begin{aligned} &\frac{1}{2}\sum_{d\mid n} \frac{n^2\varphi\left(\frac{n}{d}\right)}{d}+\frac{n}{2}\\ =&\frac{n}{2}\sum_{d\mid n} \frac{n}{d}\varphi\left(\frac{n}{d}\right)+\frac{n}{2}\\ =&\frac{n}{2}\left(\sum_{d\mid n} d\cdot \varphi(d)\right) +\frac{n}{2} \end{aligned}

设：

f(n)=∑d∣nd⋅φ(d)f(n)=\sum_{d|n} d\cdot\varphi(d)

令

n=p1c1⋅p2c2⋯pkckn=p_1^{c_1} \cdot p_2^{c_2}\cdots p_k^{c_k}

考虑 f(pc)f(p^c)，其约数只有 p0,p1,…,pcp^0,p^1,\dots,p^c

f(pc)=∑i=0cpi⋅φ(pi)=∑i=0cp2i−1⋅(p−1)f(p^c)=\sum_{i=0}^c p^i\cdot\varphi(p^i)=\sum_{i=0}^c p^{2i-1}\cdot(p-1)

考虑 f(p1c1⋅p2c2)f(p_1^{c_1}\cdot p_2^{c_2})，其中 gcd⁡(p1,p2)=1\gcd(p_1,p_2)=1

f(p1c1⋅p2c2)=∑d1∣p1c1∑d2∣p2c2d1⋅d2⋅φ(d1⋅d2)=∑d1∣p1c1∑d2∣p2c2d1φ(d1)⋅d2φ(d2)=∑d1∣p1c1d1φ(d1)⋅∑d2∣p2c2d2φ(d2)=f(p1c1)⋅f(p2c2)\begin{aligned} f(p_1^{c_1}\cdot p_2^{c_2})=&\sum_{d_1\mid p_1^{c_1}} \sum_{d_2\mid p_2^{c_2}} d_1\cdot d_2\cdot \varphi(d_1\cdot d_2)\\ =&\sum_{d_1\mid p_1^{c_1}} \sum_{d_2\mid p_2^{c_2}} d_1\varphi(d_1) \cdot d_2\varphi(d_2)\\ =&\sum_{d_1\mid p_1^{c_1}} d_1\varphi(d_1) \cdot \sum_{d_2\mid p_2^{c_2}}d_2\varphi(d_2)\\ =&f(p_1^{c_1})\cdot f(p_2^{c_2}) \end{aligned}

考虑线性筛筛 f(n)f(n) 。首先有 f(pc)=f(pc−1)+p2c−1(p−1)f(p^c)=f(p^{c-1})+ p^{2c-1}(p-1)，再考虑由 f(i),f(p)f(i),f(p) 推 f(i⋅p)f(i\cdot p)。

若 gcd⁡(i,p)=1\gcd(i,p)=1：

f(i⋅p)=f(i)⋅f(p)f(i\cdot p) = f(i)\cdot f(p)

若 p∣ip\mid i，令 i=pc−1×i′i=p^{c-1} \times i'，注意到线性筛中 pp 是 p×ip\times i 最小的素数，再额外维护一个 cnc_n 表是 nn 中最小的素数的次数即可。

Crash的数字表格

Crash的数字表格

求：

∑i=1n∑j=1mlcm⁡(i,j)(mod20101009)\sum_{i=1}^n\sum_{j=1}^m \operatorname{lcm}(i,j) \pmod{20101009}

n,m≤107n,m\le 10^7

=∑i=1n∑j=1mi×jgcd⁡(i,j)=∑i=1n∑j=1m∑d∣i,d∣j,gcd⁡(id,jd)=1i×jd=∑d=1n∑i=1⌊n/d⌋∑j=1⌊m/d⌋[gcd⁡(i,j)=1]id×jdd=∑d=1nd∑i=1⌊n/d⌋∑j=1⌊m/d⌋[gcd⁡(i,j)=1]⋅i⋅j\begin{aligned} =&\sum_{i=1}^n\sum_{j=1}^m \frac{i\times j}{\gcd(i,j)}\\ =&\sum_{i=1}^n\sum_{j=1}^m \sum_{d|i,d|j,\gcd(\frac{i}{d},\frac{j}{d})=1} \frac{i\times j}{d}\\ =&\sum_{d=1}^n \sum_{i=1}^{\lfloor n/d\rfloor}\sum_{j=1}^{\lfloor m/d\rfloor} [\gcd(i,j)=1]\frac{id\times jd}{d}\\ =&\sum_{d=1}^n d \sum_{i=1}^{\lfloor n/d\rfloor}\sum_{j=1}^{\lfloor m/d\rfloor} [\gcd(i,j)=1] \cdot i \cdot j\\ \end{aligned}

令 f(n,m)=∑i=1n∑j=1m[gcd⁡(i,j)=1]⋅i⋅jf(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m} [\gcd(i,j)=1] \cdot i \cdot j

f(n,m)=∑i=1n∑j=1mϵ(gcd⁡(i,j))⋅i⋅j=∑i=1n∑j=1m∑d∣gcd⁡(i,j)μ(d)⋅i⋅j=∑i=1n∑j=1m∑d∣i,d∣jμ(d)⋅i⋅j=∑d=1min⁡(n,m)μ(d)⋅d2∑i=1⌊n/d⌋∑j=1⌊m/d⌋i⋅j\begin{aligned} f(n,m)=&\sum_{i=1}^{n}\sum_{j=1}^{m} \epsilon(\gcd(i,j)) \cdot i \cdot j\\ =&\sum_{i=1}^n\sum_{j=1}^m \sum_{d\mid \gcd(i,j)} \mu(d)\cdot i \cdot j\\ =&\sum_{i=1}^n\sum_{j=1}^m \sum_{d\mid i,d\mid j} \mu(d)\cdot i \cdot j\\ =&\sum_{d=1}^{\min(n,m)}\mu(d)\cdot d^2 \sum_{i=1}^{\lfloor n/d\rfloor}\sum_{j=1}^{\lfloor m/d\rfloor} i\cdot j\\ \end{aligned}

令 g(x)=μ(x)⋅x2g(x)=\mu(x)\cdot x^2，线性筛可求；令 h(n,m)=∑i=1n∑j=1mi⋅j=ij(1+i)(1+j)4h(n,m)=\sum_{i=1}^n\sum_{j=1}^m i\cdot j=\frac{ij(1+i)(1+j)}{4}

f(n,m)=∑d=1min⁡(n,m)g(d)⋅h(⌊nd⌋,⌊md⌋)f(n,m)=\sum_{d=1}^{\min(n,m)} g(d) \cdot h(\left\lfloor \tfrac{n}{d}\right\rfloor,\left\lfloor \tfrac{m}{d}\right\rfloor)

预处理 g(n)g(n) 前缀和，数论分块 f(n,m)f(n,m) 在 O(n)O(\sqrt{n}) 内可求。

原式：

∑d=1nd⋅f(⌊nd⌋,⌊md⌋)\sum_{d=1}^{n} d \cdot f(\left\lfloor \tfrac{n}{d}\right\rfloor,\left\lfloor \tfrac{m}{d}\right\rfloor)

同样数论分块，算 O(n)O(\sqrt{n}) 次 ff，总复杂度 O(n)O(n)。

「SDOI2015」约数个数和

TT 祖数据，求

∑i=1n∑j=1mσ0(ij)\sum_{i=1}^n \sum_{j=1}^m \sigma_0 (ij)

T,n,m≤50000T,n,m\le 50000

（σ0(x)\sigma_0(x) 表 xx 约数个数）

有性质：

σ0(ij)=∑x∣i∑y∣j[gcd⁡(x,y)=1]\sigma_0(ij)=\sum_{x\mid i}\sum_{y\mid j} [\gcd(x,y)=1]

那么：

σ0(nm)=∑x∣n∑y∣m[gcd⁡(x,y)=1]=∑x∣n∑y∣m∑d∣gcd⁡(x,y)μ(d)=∑x∣n∑y∣m∑d∣x,d∣yμ(d)=∑d=1nμ(d)∑d∣x,x∣n∑d∣y,y∣m1=∑d∣gcd⁡(n,m)μ(d)⋅σ0(nd)⋅σ0(md)\begin{aligned} \sigma_0(nm)=&\sum_{x\mid n}\sum_{y\mid m} [\gcd(x,y)=1]\\ =&\sum_{x\mid n}\sum_{y\mid m} \sum_{d\mid \gcd(x,y)} \mu(d)\\ =&\sum_{x\mid n}\sum_{y\mid m} \sum_{d\mid x,d\mid y} \mu(d)\\ =&\sum_{d=1}^{n} \mu(d) \sum_{d\mid x,x\mid n} \sum_{d\mid y,y\mid m} 1\\ =&\sum_{d|\gcd(n,m)} \mu(d)\cdot \sigma_0\left(\frac{n}{d}\right) \cdot \sigma_0\left(\frac{m}{d}\right) \end{aligned}

回到原式：

∑i=1n∑j=1mσ0(ij)=∑i=1n∑j=1m∑d∣i,d∣jμ(d)⋅σ0(id)⋅σ0(jd)=∑d=1min⁡(n,m)μ(d)∑i=1⌊n/d⌋∑j=1⌊m/d⌋σ0(i)σ0(j)\begin{aligned} \sum_{i=1}^n\sum_{j=1}^m \sigma_0(ij)=&\sum_{i=1}^n\sum_{j=1}^m\sum_{d|i,d|j} \mu(d)\cdot \sigma_0\left(\frac{i}{d}\right) \cdot \sigma_0\left(\frac{j}{d}\right) \\ =&\sum_{d=1}^{\min(n,m)} \mu(d)\sum_{i=1}^{\left\lfloor n/d\right\rfloor}\sum_{j=1}^{\left\lfloor m/d\right\rfloor} \sigma_0(i)\sigma_0(j)\\ \end{aligned}

令 s(n)=∑i=1nσ0(i)s(n)=\sum_{i=1}^n \sigma_0(i)，那么

∑d=1min⁡(n,m)μ(d)s(⌊nd⌋)s(⌊md⌋)\sum_{d=1}^{\min(n,m)} \mu(d) s\left(\left\lfloor \frac{n}{d}\right\rfloor\right) s\left(\left\lfloor \frac{m}{d}\right\rfloor\right)

s(n)s(n) 可预处理，每次求答案数论分块即可，总复杂度 O(n+Tn)O(n+T\sqrt{n})

简单的数学题

luogu-P3768 简单的数学题

求

∑i=1n∑j=1nijgcd⁡(i,j)(modp)\sum_{i=1}^n\sum_{j=1}^n ij\gcd(i,j) \pmod{p}

n≤1010, 5×108≤p≤1.1×109,  p为质数n\le 10^{10},\,5\times 10^8 \le p \le 1.1\times 10^9,\;p\text{为质数}

用 φ∗1=id\varphi\ast 1=\mathrm{id} 反演：

∑i=1n∑j=1nijgcd⁡(i,j)=∑i=1n∑j=1nij∑d∣gcd⁡(i,j)φ(d)=∑i=1n∑j=1nij∑d∣i,d∣jφ(d)=∑d=1nφ(d)d2∑i=1⌊n/d⌋∑j=1⌊n/d⌋ij\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|\gcd(i,j)} \varphi(d)\\ =&\sum_{i=1}^n\sum_{j=1}^n ij\sum_{d|i,d|j} \varphi(d)\\ =&\sum_{d=1}^{n} \varphi(d)d^2 \sum_{i=1}^{\left\lfloor n/d\right\rfloor} \sum_{j=1}^{\left\lfloor n/d\right\rfloor} ij\\ \end{aligned}

令

s(n)=∑i=1n∑j=1nij=n2(n+1)24s(n)=\sum_{i=1}^n\sum_{j=1}^n ij=\frac{n^2(n+1)^2}{4}

O(1)O(1) 可求。带回原式：

∑d=1nφ(d)d2⋅s(⌊n/d⌋)\sum_{d=1}^{n} \varphi(d)d^2\cdot s(\left\lfloor n/d\right\rfloor)

可以数论分块 O(n)O(\sqrt{n}) ，但是需要 101010^{10} 范围的 φ(d)d2\varphi(d)d^2，需要杜教筛。

具体的，令 f(n)=φ(n)n2=(id2φ)(n)f(n)=\varphi(n)n^2=(\mathrm{id}^2\varphi)(n)，F(n)=∑i=1nf(i)F(n)=\sum_{i=1}^n f(i)，令 g(n)=(id2)(n)g(n)=(\mathrm{id}^2)(n)，G(n)=∑i=1ng(i)G(n)=\sum_{i=1}^n g(i)：

h(n)=(f∗g)(n)=∑d∣nd2φ(d)⋅n2d2=n2∑d∣nφ(d)=n3h(n)=(f\ast g)(n)=\sum_{d\mid n} d^2\varphi(d)\cdot \frac{n^2}{d^2}= n^2\sum_{d|n} \varphi(d) = n^3

H(n)=∑i=1nh(i)=∑i=1ni3=14n2(n+1)2H(n)=\sum_{i=1}^n h(i)=\sum_{i=1}^n i^3=\frac{1}{4}n^2(n+1)^2

G(n)=∑i=1ng(i)=∑i=1ni2=16n(n+1)(2n+1)G(n)=\sum_{i=1}^n g(i)=\sum_{i=1}^n i^2 =\frac{1}{6}n(n+1)(2n+1)

杜教筛：

g(1)F(n)=H(n)−∑d=2ng(d)F(⌊n/d⌋)g(1)F(n) = H(n) - \sum_{d=2}^n g(d) F(\left\lfloor n/d\right\rfloor)