题目大意

我们称一个高斯整数 $a + b\text{i}$（其中 $a, b$ 是整数）是整数 $k$ 的约数，如果存在另一个高斯整数 $c + d\text{i}$ 使得：

$$(a + b\text{i})(c + d\text{i}) = k$$

给定 $n$，求所有满足 $a > 0$ 的约数 $a + b\text{i}$ 的 $a$ 之和（对 $1$ 到 $n$ 的所有 $k$ 求和）。

问题分析

高斯整数的约数

在 Gaussian Integers（高斯整数）中，一个整数 $k$ 的约数 $a + b\text{i}$ 需要满足：

• $a, b$ 是整数
• $a^2 + b^2$ 整除 $k$

这是因为：

$$(a + b\text{i})(c + d\text{i}) = (ac - bd) + (ad + bc)\text{i} = k $$

由于 $k$ 是实数，所以 $ad + bc = 0$，且 $ac - bd = k$。通过计算可以得到 $k = (a^2 + b^2)(c^2 + d^2)/(a^2 + b^2)$ 的某种形式，实际上最终结论是：$a^2 + b^2$ 必须整除 $k$。

更准确地说，$z = a + b\text{i}$ 是 $k$ 的约数当且仅当 $z$ 的范数 $N(z) = a^2 + b^2$ 整除 $k$。

问题转化

因此，原问题转化为： 对于每个 $k$ 从 $1$ 到 $n$，求所有满足 $a > 0$ 且 $a^2 + b^2$ 整除 $k$ 的 $a$ 之和。

设答案为：

$$\text{ans} = \sum_{k=1}^n \sum_{\substack{a>0 \\ a^2+b^2 \mid k}} a $$

交换求和顺序：

$$\text{ans} = \sum_{a=1}^n \sum_{b=-\infty}^{\infty} \sum_{\substack{k=1 \\ a^2+b^2 \mid k}}^n a \cdot [a>0] $$

由于 $a^2+b^2 \mid k$，设 $k = m(a^2+b^2)$，则：

$$\text{ans} = \sum_{a=1}^n \sum_{b=-\infty}^{\infty} a \cdot \left\lfloor \frac{n}{a^2+b^2} \right\rfloor \cdot [a^2+b^2 \leq n] $$

进一步简化

由于表达式关于 $b$ 对称，我们可以只考虑 $b \geq 0$ 然后乘以相应的系数：

• 当 $b = 0$ 时，贡献为 $1$ 倍
• 当 $b > 0$ 时，贡献为 $2$ 倍（因为 $b$ 和 $-b$ 都对应相同的 $a^2+b^2$）

所以：

$$\text{ans} = \sum_{a=1}^{\lfloor \sqrt{n} \rfloor} \sum_{b=0}^{\lfloor \sqrt{n-a^2} \rfloor} a \cdot c_b \cdot \left\lfloor \frac{n}{a^2+b^2} \right\rfloor $$

其中 $c_b = \begin{cases} 1 & \text{if } b = 0 \\ 2 & \text{if } b > 0 \end{cases}$

算法实现

直接枚举（适合小数据）

对于 $n \leq 10^7$，我们可以直接枚举 $a$ 和 $b$：

#include <iostream>
#include <cmath>
using namespace std;

const int MOD = 1004535809;

int main() {
    int n;
    cin >> n;
    long long ans = 0;
    int sqrt_n = sqrt(n);
    
    for (int a = 1; a <= sqrt_n; a++) {
        for (int b = 0; a*a + b*b <= n; b++) {
            if (b == 0) {
                ans = (ans + 1LL * a * (n / (a*a))) % MOD;
            } else {
                ans = (ans + 2LL * a * (n / (a*a + b*b))) % MOD;
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

优化算法（适合大数据）

对于 $n$ 达到 $10^{10}$ 的情况，我们需要更高效的算法。

观察求和式：

$$\text{ans} = \sum_{d=1}^n \left\lfloor \frac{n}{d} \right\rfloor \cdot f(d) $$

其中 $f(d)$ 表示所有满足 $a^2+b^2 = d$ 且 $a > 0$ 的 $a$ 之和（考虑 $b=0$ 贡献 $1$ 倍，$b>0$ 贡献 $2$ 倍）。

我们可以用数论分块来优化，预处理 $f(d)$ 的前缀和。

复杂度分析

• 直接枚举：$O(n)$ 对于 $n \leq 10^7$ 可行
• 优化算法：$O(n^{2/3})$ 或 $O(\sqrt{n})$ 对于更大的 $n$

总结

本题的关键在于理解高斯整数约数与范数 $a^2+b^2$ 的关系，通过交换求和顺序将问题转化为数论分块的形式，从而设计出高效的算法。

对于竞赛中的不同数据范围，需要选择相应复杂度的算法来实现。