136. 唯一差(Singleton Difference)

正整数\(x, y, z\)是等差数列的连续三项。对于正整数\(n\)，考虑方程\(x^2 - y^2 - z^2 = n\)。当\(n = 20\)时，该方程恰好有一个解：\(13^2 - 10^2 - 7^2 = 20\)。

在小于一百的\(n\)值中，有二十五个\(n\)使得该方程有唯一解。

在小于五千万的\(n\)值中，有多少个\(n\)使得该方程有唯一解？

一、数学背景

设\(x, y, z\)为等差数列的连续三项，公差为\(d > 0\)。令\(x = y + d, z = y - d\)，由\(z > 0\)得\(y > d\)。

将参数代入原方程：

$$ \begin{aligned} x^2 - y^2 - z^2 &= (y+d)^2 - y^2 - (y-d)^2 \\ &= (y^2 + 2yd + d^2) - y^2 - (y^2 - 2yd + d^2) \\ &= -y^2 + 4yd \\ &= y(4d - y) \end{aligned} $$

令\(k = 4d - y\)，则\(n = y \cdot k\)。由此可得约束条件：

因此，\(n\)有解当且仅当存在正整数对\((y, k)\)满足： - \(n = y \cdot k\) - \(y + k \equiv 0 \pmod{4}\) - \(0 < k < 3y\)

方程有唯一解等价于：恰好存在一对\((y, k)\)满足上述三个条件。

二、算法设计

采用筛法思想：遍历所有可能的\(y\)值，对于每个\(y\)遍历所有满足条件的\(k\)值，计算\(n = y \cdot k\)并增加该\(n\)的计数器。最后统计计数恰好为1的\(n\)的个数。

对于每个\(y\)，\(k\)的取值范围由两个上界决定： - \(k < 3y\)（数学约束） - \(k < \frac{N}{y}\)（\(n < N\)的约束，\(N = 5 \times 10^7\)）

\(k\)的最小值由同余条件\(k \equiv -y \pmod{4}\)决定。

复杂度估算： 总操作次数约为\(\sum_{y=1}^{N} \frac{\min(3y, N/y)}{4}\)。当\(y \le \sqrt{N/3}\)时内循环约\(3y/4\)次；当\(y > \sqrt{N/3}\)时约\(N/(4y)\)次。总和约为\(O(N \log N)\)级别，对于\(N = 5 \times 10^7\)，实际操作次数约\(1.2 \times 10^8\)次，在Python中可于20秒内完成。

三、复杂度分析

四、代码实现与说明

#!/usr/bin/env python3
"""
Project Euler Problem 136: Singleton Difference
"""

import time


def solve(n_limit):
    """Count numbers n < n_limit with exactly one representation."""
    counts = [0] * n_limit

    y = 1
    while y < n_limit:
        # k must satisfy: k ≡ -y (mod 4)
        k_start = (-y) % 4
        if k_start == 0:
            k_start = 4
        if k_start >= 3 * y:
            y += 1
            continue

        k_max = min(3 * y - 1, (n_limit - 1) // y)

        for k in range(k_start, k_max + 1, 4):
            n = y * k
            if n < n_limit:
                counts[n] += 1

        y += 1

    result = sum(1 for c in counts if c == 1)
    return result

solve函数——初始化

solve函数——确定k的起始值

solve函数——遍历k值

solve函数——统计结果

def main():
    n_limit = 50000000
    start = time.time()
    answer = solve(n_limit)
    elapsed = time.time() - start

    print(f"Answer: {answer}")
    print(f"Time: {elapsed:.3f}s")


if __name__ == "__main__":
    main()

main函数

 

本站所有文章如非特别声明皆为原创，转载请与作者本人联系并注明出处(原文链接)。 如对文章有任何疑问或需指出错误，可以此页面提出问题，我会尽量及时回复。

←返回主页