127. abc击中数(abc-hits)

\(n\)的根数（radical），记为\(\operatorname{rad}(n)\)，是\(n\)的不同质因子的乘积。例如，\(504 = 2^3 \times 3^2 \times 7\)，所以\(\operatorname{rad}(504) = 2 \times 3 \times 7 = 42\)。

若正整数三元组\((a, b, c)\)满足以下四个条件，则称其为abc击中数（abc-hit）：

  1. \(\gcd(a, b) = \gcd(a, c) = \gcd(b, c) = 1\)
  2. \(a < b\)
  3. \(a + b = c\)
  4. \(\operatorname{rad}(abc) < c\)

例如\((5, 27, 32)\)是一个abc击中数，因为： - 三个最大公约数条件成立 - \(5 < 27\) - \(5 + 27 = 32\) - \(\operatorname{rad}(4320) = 30 < 32\)

abc击中数相当稀少，对于\(c < 1000\)，仅有三十一个abc击中数，且\(\sum c = 12523\)。

求对于\(c < 120000\)的\(\sum c\)。

一、数学背景

本题涉及数论中的根数（radical）概念和abc猜想的相关组合结构。

关键性质1——互质性的简化： 由于\(a + b = c\)，三个\(\gcd\)条件实际上退化为一个： - \(\gcd(a, c) = \gcd(a, a+b) = \gcd(a, b)\) - \(\gcd(b, c) = \gcd(b, a+b) = \gcd(b, a)\) 因此只需验证\(\gcd(a, b) = 1\)即可保证三项两两互质。

关键性质2——根数的可乘性： 对于两两互质的\(a, b, c\)，有\(\operatorname{rad}(abc) = \operatorname{rad}(a) \cdot \operatorname{rad}(b) \cdot \operatorname{rad}(c)\)。这是因为不同数的不同质因子之间没有交集。

因此条件4变为：\(\operatorname{rad}(a) \cdot \operatorname{rad}(b) \cdot \operatorname{rad}(c) < a + b\)。

关键性质3——搜索空间的约束： 由条件4可得\(\operatorname{rad}(a) \cdot \operatorname{rad}(b) < a + b < 120000\)。这意味着两个数的根数之积有严格上界，大幅限制了需要搜索的\((a, b)\)对。

二、算法设计

步骤1：筛法计算根数。 使用类似埃拉托斯特尼筛法的方式，对于每个质数\(p\)，将其所有倍数乘以\(p\)，最终得到每个数的\(\operatorname{rad}(n)\)。

步骤2：按根数值分组。 将所有\(n\)（\(1 \le n < 120000\)）按其根数值归类到字典中。这使得我们可以按根数对而非逐个数值来搜索。

步骤3：在根数对上搜索。 对于满足\(r_a \cdot r_b < 120000\)的每对根数值\((r_a, r_b)\)： - 遍历根数为\(r_a\)的所有\(a\)值 - 遍历根数为\(r_b\)的所有\(b\)值（要求\(b > a\)） - 计算\(c = a + b\)，检查\(c < 120000\) - 验证\(\gcd(a, b) = 1\) - 验证\(r_a \cdot r_b \cdot \operatorname{rad}(c) < c\)

为什么根数分组有效： 约束\(r_a \cdot r_b < 120000\)意味着两个根数不能同时很大——至少一个小于\(\sqrt{120000} \approx 346\)。对于大根数值，能与之配对的根数范围非常有限，这极大地剪枝了搜索空间。

三、复杂度分析

四、代码实现与说明

#!/usr/bin/env python3
"""
Project Euler Problem 127: abc-hits
"""

import time


def compute_radicals(limit):
    """Compute rad(n) for all n from 1 to limit using a sieve."""
    rad = [1] * (limit + 1)
    rad[0] = 0
    for p in range(2, limit + 1):
        if rad[p] == 1:  # p is prime
            step = p
            for multiple in range(p, limit + 1, step):
                rad[multiple] *= p
    return rad

compute_radicals函数——筛法计算根数

def gcd(a, b):
    """Euclidean algorithm for greatest common divisor."""
    while b:
        a, b = b, a % b
    return a


def solve(limit):
    """Find sum of c for abc-hits with c < limit."""
    rad = compute_radicals(limit)

    # Group numbers by radical value
    groups = {}
    for n in range(1, limit):
        r = rad[n]
        groups.setdefault(r, []).append(n)

    radical_values = sorted(groups.keys())

    total = 0
    count = 0

    for ra in radical_values:
        max_rb = (limit - 1) // ra
        list_a = groups[ra]

        for rb in radical_values:
            if rb > max_rb:
                break
            if ra * rb >= limit:
                continue

            list_b = groups[rb]

            for a in list_a:
                if a >= limit // 2:
                    continue
                for b in list_b:
                    if b <= a:
                        continue
                    c = a + b
                    if c >= limit:
                        break
                    if ra * rb * rad[c] < c and gcd(a, b) == 1:
                        total += c
                        count += 1

    print(f"  Found {count} abc-hits")
    return total

gcd函数

solve函数——根数分组

solve函数——双层循环搜索

def main():
    limit = 120000
    start = time.time()
    answer = solve(limit)
    elapsed = time.time() - start

    print(f"Sum of c for c < {limit}: {answer}")
    print(f"Time: {elapsed:.3f}s")

    # Verify with sample test
    sample_limit = 1000
    sample_answer = solve(sample_limit)
    print(f"Verification: sum for c < {sample_limit} = {sample_answer} (expected 12523)")


if __name__ == "__main__":
    main()

main函数

 

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

←返回主页