Description：

一个棋盘， $(i,j)$ 上的数是 $f(i,j)$ ，要求任意时刻满足： $f(i,j)=f(j,i),j\times f(i,i+j)=(i+j)\times f(i,j)$ 。

支持修改某一个位置上的值并维护这个棋盘，保证任意时刻棋盘都为整数，询问前 $k\times k$ 的和。

$1\leqslant n\leqslant 10^6,1\leqslant q\leqslant 10^4$

Solution：

首先有： $$ \frac{f(i,i+j)}{i+j}=\frac{f(i,j)}j\\ \frac{f(i,i+j)}{i\times(i+j)}=\frac{f(i,j)}{i\times j} $$ 也就是说： $$ \frac{f(b,a)}{b\times a}=\frac{f(b,a\%b)}{b\times(a\%b)} $$ 也就是说设 $g(a,b)=\frac{f(a,b)}{a\times b}$ ，那么： $$ g(a,b)=g(b,a)=g(b,a\%b)=g(b,a-b)=g(\gcd(a,b),\gcd(a,b)) $$ 设 $d=\gcd(a,b)$ ，那么： $$ f(a,b)=a\times b\times g(a,b)=a\times b\times g(d,d)=a\times b\times \frac{f(d,d)}{d^2}=\frac{a\times b}{d^2}f(d,d) $$ 也就是说整个矩阵可以由这一条对角线确定，更重要的是，每修改一个格子上的值，对角线上的格子只有 $f(\gcd(a,b),\gcd(a,b))$ 一个格子会发生变化，考虑假如已知对角线上所有格子的值，那么如何求答案： $$ \begin{align} ans&=\sum_{i=1}^k\sum_{j=1}^kf(i,j)\\ &=\sum_{i=1}^k\sum_{j=1}^k\frac{i\times j}{\gcd(i,j)^2}f(\gcd(i,j),\gcd(i,j))\\ &=\sum_{d=1}^k\frac{f(d,d)}{d^2}\sum_{i=1}^k\sum_{j=1}^ki\times j\times [\gcd(i,j)=d]\\ &=\sum_{d=1}^kf(d,d)\sum_{i=1}^{\lfloor\frac k d\rfloor}\sum_{j=1}^{\lfloor\frac k d\rfloor}ij\varepsilon(\gcd(i,j)) \end{align} $$ 设 $\begin{align}G(k)=\sum_{i=1}^k\sum_{j=1}^kij\varepsilon(\gcd(i,j))\end{align}$

那么显然求出 $G(k)$ 之后就可以除法分块求答案了。

然后求 $G$ 就是套路了： $$ \begin{align} G(k)&=\sum_{i=1}^k\sum_{j=1}^kij\varepsilon(\gcd(i,j))\\ &=2\times\sum_{i=1}^k\sum_{j=1}^{i-1}ij\varepsilon(\gcd(i,j))+1\\ &=2\times\sum_{i=2}^ki\sum_{j=1}^ij[\gcd(i,j)=1]+1\\ &=2\times \sum_{i=2}^ki\frac{i(\varphi(i)+\varepsilon(i))}{2}+1\\ &=\sum_{i=1}^ki^2\varphi(i) \end{align} $$ 这个显然可以线性筛预处理然后求个前缀和。

由于要除法分块所以我们要一个支持 $O(\sqrt n)$ 修改 $O(1)$ 查询前缀和的数据结构，显然分块可以。

Code：