题目分析

我们有一个无穷表格 f(a,b)，满足：

1.对称性：

$$f(a,b)=f(b,a)$$

2.函数方程：

$$b×f(a,a+b)=(a+b)×f(a,b)$$

初始 f(a,b)=a×b。

---

关键结论

通过函数方程和对称性，可以推导出：

$$f(a,b)=a×b×H(gcd(a,b))$$

其中 H 是一个整数序列，初始 H(d)=1。

---

修改操作

修改 f(a,b) 为 x 时，令 d=gcd(a,b)，则：

$$H(d)= x/(a×b)$$

修改会波及所有 gcd(a′,b′)=d 的位置，相当于更新了 H(d)。

---

查询操作

查询前 k 行 k 列的和:

$$S(k) = \sum_{i=1}^k \sum_{j=1}^k i \times j \times H(\gcd(i,j)) $$

通过莫比乌斯反演，可以推出：

$$S(k) = \sum_{m=1}^k \left( \frac{ \lfloor k/m \rfloor \cdot (\lfloor k/m \rfloor + 1) }{2} \right)^2 \cdot F(m) $$

其中

$$F(m) = m^2 \cdot \sum_{d|m} H(d) \cdot \mu\left(\frac{m}{d}\right) $$

μ 是莫比乌斯函数。

---

算法步骤

1.预处理 μ 和初始 F 数组。

2.修改 (a,b,x)： 计算 d=gcd(a,b) 更新 H(d)=x/(a×b) 更新所有 m 满足d∣m 的 F(m) 更新 F 的前缀和

3.查询 k： 使用整除分块，在 O($\sqrt{k}$)时间内计算 S(k)