求n表示为三平方和的分拆数：快速算法求解问询

这个问题我之前研究过，刚好能给你清晰的解答！首先明确：要计算的是A000164对应的数值——也就是将n表示为三个平方和的有序表示数（区分顺序和符号），在n<1e9且1秒时间限制下，O(n)的算法完全不可能（1e9次操作远超过1秒能处理的量级），必须用数论公式结合因数分解来实现，时间复杂度可以降到O(√n)，完全满足要求。

步骤1：先判断是否存在合法表示 #

根据Legendre三平方定理，n无法表示为三个平方和当且仅当n可以写成n=4^k*(8m+7)的形式。我们可以通过以下步骤快速判断：

• 反复将n除以4，直到结果不再被4整除，记录除以4的次数k，得到剩余的m；
• 如果m除以8的余数是7，直接返回0（没有任何表示方式）；
• 否则，继续计算具体的表示数。

步骤2：用除数和函数计算表示数 #

A000164的表示数可以通过数论公式转化为对奇数因数和的计算，核心思路是：

1. 先把n化简为n=4^k * m（m不被4整除）；
2. 计算m的奇数因数和（或m/2的奇数因数和，取决于m的奇偶性）；
3. 根据m的模8结果，套用对应的系数公式得到最终结果。

具体公式（对应A000164的定义）：

• 若m是奇数（m≡1,3,5 mod8）：表示数 = 12 * σ_odd(m) * 2^k
• 若m是偶数（m≡2,6 mod8，此时m=2*t，t为奇数）：表示数 = 12 * σ_odd(t) * 2^k

这里的σ_odd(x)指的是x的所有奇数正因数之和。

步骤3：高效计算奇数因数和σ_odd(x) #

计算σ_odd(x)的关键是对x的奇数部分进行因数分解：

1. 先去掉x中的所有2的因子，得到纯奇数x_odd；
2. 对x_odd进行暴力试除分解（因为x最大为1e9，√x_odd最多3e4次循环，完全在1秒内完成）；
3. 对于每个奇素数因子p的幂次e，计算1+p+p²+...+p^e，再将所有结果相乘得到σ_odd(x)。

伪代码实现示例 #

def count_three_squares(n):
    # 步骤1：判断是否为4^k*(8m+7)
    k = 0
    m = n
    while m % 4 == 0:
        m = m // 4
        k += 1
    if m % 8 == 7:
        return 0

    # 辅助函数：计算x的奇数因数和
    def sigma_odd(x):
        # 去掉所有2的因子
        x_odd = x
        while x_odd % 2 == 0:
            x_odd = x_odd // 2
        res = 1
        d = 3
        while d * d <= x_odd:
            if x_odd % d == 0:
                cnt = 0
                while x_odd % d == 0:
                    cnt += 1
                    x_odd = x_odd // d
                # 计算1+d+d²+...+d^cnt
                s = 0
                current = 1
                for _ in range(cnt + 1):
                    s += current
                    current *= d
                res *= s
            d += 2
        if x_odd > 1:
            res *= (1 + x_odd)
        return res

    # 步骤2：根据m的情况计算结果
    if m % 2 == 1:
        sigma = sigma_odd(m)
        return 12 * sigma * (2 ** k)
    else:
        # m是偶数且不被4整除，即m=2*t，t为奇数
        t = m // 2
        sigma = sigma_odd(t)
        return 12 * sigma * (2 ** k)

总结 #

• 完全不需要O(n)的算法，纯数论方法就能做到O(√n)的时间复杂度，轻松处理n<1e9的情况；
• 核心是利用Legendre定理快速排除无解情况，再通过因数分解计算除数和得到表示数；
• 代码实现上，暴力试除因数分解就足够高效，不需要复杂的优化。

内容的提问来源于stack exchange，提问作者Dmitry Pyatin