T1
Statement
对于 \(n,m,T\le50000\)，求 \(\sum_{i\in[1..n]}\sum_{j\in[1..m]}d(ij)\)
Solution
因为 \(d(ij)=\sum_{u|i}\sum_{v|j}[\gcd(u,v)=1]\)
\[ \begin{aligned}&\sum_{i\in[1..n]}\sum_{j\in[1..m]}d(ij)\\=&\sum_{i\in[1..n]}\sum_{j\in[1..m]}\sum_{u\mid i}\sum_{v\mid j}[\gcd(u,v)=1]\\=&\sum_{i\in[1..n]}\sum_{j\in[1..m]}\sum_{u\mid i}\sum_{v\mid j}\sum_{d\mid u\land d\mid v}\mu(d)\\=&\sum_{i\in[1..n]}\sum_{j\in[1..m]}\sum_{d\mid i\land d\mid j}d\left(\dfrac id\right)d\left(\dfrac jd\right)\mu(d)\\=&\sum_{d\in[1..\min(n,m)]}\mu(d)\sum_{i\in[1..\left\lfloor\frac nd\right\rfloor]}d(i)\sum_{j\in[1..\left\lfloor\frac md\right\rfloor]}d(j)\end{aligned}
\]
预处理 \(\mu\) 和 \(d\) 的前缀和，这样每次可以 \(\mathcal O(\sqrt n)\) 计算.
T2
Statement
对于 \(n,m\le10^7\)，\(T\le10^4\)，求有多少对 \((x,y)\) 满足 \(x\le n\land y\le m\)，且 \(\gcd(x,y)\) 是一个质数。
Solution
记 \(\mathbb P\) 为质数集合
\[ \begin{aligned}&\sum_{x=1}^n\sum_{y=1}^m\sum_{p\in\mathbb P}[\gcd(x,y)=p]\\=&\sum_{p\in\mathbb P}\sum_{x=1}^{\left\lfloor\frac np\right\rfloor}\sum_{y=1}^{\left\lfloor\frac mp\right\rfloor}[\gcd(x,y)=1]\\=&\sum_{p\in\mathbb P}\sum_{d=1}^{\min(\left\lfloor\frac np\right\rfloor,\left\lfloor\frac mp\right\rfloor)}\mu(d)\left\lfloor\dfrac n{pd}\right\rfloor\left\lfloor\dfrac m{pd}\right\rfloor\\=&\sum_{t=1}^{\min(n,m)}\left\lfloor\dfrac nt\right\rfloor\left\lfloor\dfrac mt\right\rfloor\sum_{d\mid t\land\frac td\in\mathbb P}\mu(d)\end{aligned}
\]
右边可以埃氏筛预处理；左边可以整除分块，\(\Theta(T\sqrt n+n\ln\ln n)\)
T3
Statement
对于 \(T\le10^4,n,m\le10^7\)，求
\[ \sum_{i=1}^n\sum_{j=1}^m\text{lcm}(i,j)
\]
Solution
\[ \begin{aligned}&\sum_{i=1}^n\sum_{j=1}^m\text{lcm}(i,j)\\=&\sum_{i=1}^n\sum_{j=1}^m\dfrac{ij}{\gcd(i,j)}\\=&\sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^{\min(i,j)}[\gcd(i,j)=d]\dfrac{ij}d\\=&\sum_{d=1}^{\min(n,m)}\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]\dfrac{ij}d\\=&\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{\left\lfloor\frac nd\right\rfloor}\sum_{i=1}^{\left\lfloor\frac md\right\rfloor}[\gcd(i,j)=1]ijd\\=&\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{\left\lfloor\frac nd\right\rfloor}\sum_{j=1}^{\left\lfloor\frac md\right\rfloor}\sum_{p\mid i\land p\mid j}\mu(p)ijd\\=&\sum_{d=1}^{\min(n,m)}d\sum_{p=1}^{\min\left(\left\lfloor\frac nd\right\rfloor,\left\lfloor\frac md\right\rfloor\right)}\mu(p)\sum_{i=1}^{\left\lfloor\frac nd\right\rfloor}\sum_{j=1}^{\left\lfloor\frac nd\right\rfloor}ij\\=&\sum_{d=1}^{\min(n,m)}d\sum_{p=1}^{\min\left(\left\lfloor\frac nd\right\rfloor,\left\lfloor\frac md\right\rfloor\right)}\mu(p)C_{\left\lfloor\frac nd\right\rfloor}^2C_{\left\lfloor\frac md\right\rfloor}^2\\=&\sum_{d=1}^{\min(n,m)}C_{\left\lfloor\frac nd\right\rfloor}^2C_{\left\lfloor\frac md\right\rfloor}^2d\sum_{p=1}^{\min\left(\left\lfloor\frac nd\right\rfloor,\left\lfloor\frac md\right\rfloor\right)}\mu(p)\end{aligned}
\]
这个式子可以整除分块，因为 \(\left\lfloor\dfrac nd\right\rfloor\) 共 \(\sqrt n\) 种，\(m\) 也一样
右边的 Sigma 可以预处理前缀和
\(\mathcal O(n+T\sqrt n)\)
T4
Statement
给定组数 \(T=10^4\)，全局变量 \(1\le K<2^{31}\)，每组数据给出 \(N\le10^7\)，已知 \(Q=2^{32}\)，求
\[ \sum_{i=1}^N\sum_{j=1}^N(i+j)^K\gcd(i,j)\mu^2(\gcd(i,j))\bmod Q
\]
Solution
模 \(Q\) 直接无视
\[ \begin{aligned}Ans&=\sum_{i=1}^N\sum_{j=1}^N(i+j)^K\gcd(i,j)\mu^2(\gcd(i,j))\\&=\sum_{d=1}^Nd\mu^2(d)\sum_{i=1}^N\sum_{j=1}^N[\gcd(i,j)=d](i+j)^K\\&=\sum_{d=1}^Nd\mu^2(d)\sum_{i=1}^{\left\lfloor\frac Nd\right\rfloor}\sum_{j=1}^{\left\lfloor\frac Nd\right\rfloor}[\gcd(i,j)=1]d^K(i+j)^K\\&=\sum_{d=1}^Nd^{K+1}\mu^2(d)\sum_{i=1}^{\left\lfloor\frac Nd\right\rfloor}\sum_{j=1}^{\left\lfloor\frac Nd\right\rfloor}(i+j)^K\sum_{p\mid i\land p\mid j}\mu(p)\\&=\sum_{d=1}^Nd^{K+1}\mu^2(d)\sum_{p=1}^{\left\lfloor\frac Nd\right\rfloor}\mu(p)p^K\sum_{i=1}^{\left\lfloor\frac N{dp}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac N{dp}\right\rfloor}(i+j)^K\end{aligned}
\]
观察到 \(g(m)=\sum_{i=1}^m\sum_{j=1}^m(i+j)^K\) 可通过预处理 \(f_0(m)=m^K\)、\(f_1(m)=\sum_{i=1}^mi^K\)、\(f_2(m)=\sum_{i=1}^mi\cdot i^K\)、\(f_3(m)=\sum_{i=1}^m(m-i+1)\cdot i^K\) 来 \(\mathcal O(1)\) 求出：\(g(m)=f_2(m+1)-f_1(m+1)+f_3(2m)-f_3(m+1)\)；
而 \(f_0\) 可以线性筛，\(f_1,f_2,f_3\) 都可以用 \(f_0\) 线性递推，故预处理是线性的，\(g\) 也能预处理；
\[ \begin{aligned}Ans&=\sum_{d=1}^Nd^{K+1}\mu^2(d)\sum_{p=1}^{\left\lfloor\frac Nd\right\rfloor}\mu(p)p^Kg\left(\left\lfloor\frac N{dp}\right\rfloor\right)\\&=\sum_{d=1}^N\sum_{p=1}^{\left\lfloor\frac Nd\right\rfloor}(dp)^Kg\left(\left\lfloor\dfrac N{dp}\right\rfloor\right)d\cdot\mu^2(d)\mu(p)\\&=\sum_{t=1}^Nt^Kg\left(\left\lfloor\dfrac Nt\right\rfloor\right)\sum_{d\mid t}d\cdot\mu^2(d)\mu\left(\dfrac td\right)\end{aligned}
\]
观察到第二个 Sigma 是个积性函数，故可以线性筛，然后处理出前缀和；整个式子中 \(\left\lfloor\frac Nt\right\rfloor\) 有 \(\sqrt N\) 种，故可以整除分块，\(\mathcal O(N+T\sqrt N)\)
它 \(=h(x)\) 的筛法：
\[ h(x)=\begin{cases}1&,x=1\\\mu(x)+\text P(x)\cdot\mu\left(\frac x{\text P(x)}\right)&,x\not=1\land x=\text{PA}(x)\\h\left(\frac x{\text{PA}(x)}\right)\cdot h(\text{PA}(x))&,x\not=1\land x\not=\text{PA}(x)\end{cases}
\]
