T0

所在行 $x$ 应为 $x=\operatorname{lcm}(a_i)$, 所在列 $y$ 应满足 $a_i|y+i$, 用 EXCRT 求解后验证即可.

T1

T2

$$ f(n){=\sum_{i=1}^n\frac{\operatorname{lcm}(n,i)}n=\sum_{i=1}^n\frac i{\gcd(n,i)}\\ =\sum_{i|n}\sum_{j=1}^n\frac{j[\gcd(n,j)=i]}i=\sum_{i|n}\sum_{j=1}^{n/i}j\left[\gcd\left(\frac ni,j\right)=1\right]\\ =\sum_{i|n}\sum_{j=1}^ij[\gcd(i,j)=1] } $$

考虑 $\gcd(u,v)=\gcd(u-v,v)$, 故有 $\gcd(u,v)=1\Leftrightarrow\gcd(u-v,v)=1$.
记 $S=\sum_{i=1}^n[i\gcd(n,i)=1]$, 则

$$ 2S{=\sum_{i=1}^ni[\gcd(n,i)=1]+\sum_{i=1}^ni[\gcd(n,i)=1]\\ =\sum_{i=1}^ni[\gcd(n,i)=1]+\sum_{i=1}^n(n-i)[\gcd(n,i)=1]\\ =n\sum_{i=1}^n[\gcd(n,i)=1]=n\varphi(n) } $$

同时若 $\gcd(n,n)=1$ 则 $n=1$. 故 $S=\frac{n\varphi(n)+[n=1]}2$.

故有

$$ f(n)=\frac{1+\sum_{i|n}i\varphi(i)}2 $$

令 $g(n)=\sum_{i|n}i\varphi(i)$, 则

$$ \sum_{i=1}^ng(n)=\sum_{i=1}^n\sum_{j|i}j\varphi(j)=\sum_i\left\lfloor\frac ni\right\rfloor i\varphi(i) $$

即从对每个 $i$ 枚举因数 $j$ 变为枚举每个数 $i$ 作为因数出现了多少次, 需要在每个 $\left\lfloor\frac ni\right\rfloor$ 处求出 $i\varphi(i)$ 的前缀和.

$n=\sum_{i|n}\varphi(n)$,证明链接 .

写成 $n=\sum_{ij=n}\varphi(i)$ 的形式, 两边同时乘上 $n=ij$ 就得到 $n^2=\sum_{ij=n}i\varphi(i)j$, 即

$$ \{i\varphi(i)\}\cdot\{j\}=\{i^2j^2\} $$

然后做杜教筛即可.

T3

$$ f(n)=\sum_{i|n}\gcd\left(i,\frac ni\right)=\sum_{i|n}\sum_{j|i~\text{and}~j|(n/i)}\varphi(j) $$

出现后半部分的原因是枚举 $\gcd$ 的所有因数, 然后 $n=\sum_{i|n}\varphi(n)$.

$$ \sum_{i=1}^nf(i){=\sum_{i=1}^n\sum_{j|i}\sum_{k|j~\text{and}~k|(i/j)}\varphi(k)\\ =\sum_{i=1}^n\sum_{j}\varphi(j)\sum_{j|k}\sum_{j|l}[i=kl]\\ =\sum_{i}\varphi(i)\sum_{j}\sum_{k}[n\ge i^2jk]\\ =\sum_{i}\varphi(i)\sum_{j}\sum_{k}\left[\frac n{i^2}\ge jk\right]\\ =\sum_{i}\varphi(i)\sum_{j=1}^{n/i^2}\left\lfloor\frac n{i^2j}\right\rfloor } $$

T4

记 $n=p_1^{q_1}p_2^{q_2}\ldots p_k^{q_k}$, 则

$$ f(n)=p_1^{\lfloor q_1/2\rfloor}p_2^{\lfloor q_2/2\rfloor}\ldots p_k^{\lfloor q_k/2\rfloor}=\frac n{\prod_{i=1}^kp_i^{\lceil q_i/2\rceil}}\\ $$

$n|m\Rightarrow \frac nm=\sum_{i=1}^n[m|i]$, 即考虑 $[1,n]$ 中有多少 $m$ 的倍数.

$$ f(n)=\sum_{i=1}^n\left[{\prod\nolimits_{j=1}^kp_j^{\lceil q_j/2\rceil}}|i\right]=\sum_{i=1}^n\left[n|i^2\right]\\ \sum_{i=1}^nf(i){=\sum_{i=1}^n\sum_{j=1}^i\left[i|j^2\right]=\sum_{i=1}^n\sum_{j=1}^i\sum_k\left[ik=j^2\right]\\ =\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^j\sum_{l=1}^j[\gcd(j,l)=i]\left[jl=k^2\right]\\ =\sum_{i=1}^n\sum_{j=1}^{n/i}\sum_{k=1}^j[\gcd(j,k)=1][j,k\text{为完全平方数}]\\ =\sum_{i=1}^n\sum_{j=1}^\sqrt{n/i}\sum_{k=1}^j[\gcd(j,k)=1]=\sum_{i=1}^n\sum_{j=1}^\sqrt{n/i}\varphi(j)\\ =\sum_{i=1}^\sqrt n\varphi(i)\left\lfloor\frac n{i^2}\right\rfloor } $$

或者 powerful number 筛之类的后现代科技, 但是窝不会 /cy.

T5

记 $f(n)=\frac n{\min(p)}$ 满足 $p\ge2$ 且 $p|n$, 则 $\operatorname{sgcd}(u,v=f(\gcd(u,v))$.

$$ \sum_{i=1}^n\sum_{j=1}^n\operatorname{sgcd}(i,j)^k{=\sum_{i}\sum_{j=1}^n\sum_{k=1}^n[\gcd(j,k)=i]f(i)^k\\ =\sum_{i}\sum_{j=1}^{n/i}\sum_{k=1}^{n/i}[\gcd(j,k)=1]f(i)^k } $$

$$ \sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1]{=2\sum_{i=1}^n\sum_{j=i}^n[\gcd(i,j)=1]-1\\ =2\sum_{i=1}^n\varphi(i)-1 } $$

$$ \sum_{i=1}^n\sum_{j=1}^n\operatorname{sgcd}(i,j)^k=\sum_{i}f(i)^k\left(2\sum_{j=1}^{n/i}\varphi(j)-1\right) $$

则后半部分用杜教筛对每个 $\left\lfloor\frac ni\right\rfloor$ 算.