Python暴力破解方程程序优化求助：如何提升运行速度？

Hey there! Let's tackle this performance issue head-on. Your current brute-force approach uses nested loops over a and b, which gives you O(500*1500) = 750,000 iterations—no wonder it slows down when hunting for multiple results. The key here is to reduce the problem from a double loop to a single loop by rearranging the equation mathematically, so we can solve for b directly instead of checking every possible value.

First, let's rewrite your original equation to use only integer arithmetic (this avoids floating-point errors and speeds up calculations). Starting with your equation:

(0.5k -1)*a(a+1)(2a+1)/6 + (-0.5k +2)*a(a+1)/2 = (0.5k -1)*b² + (-0.5k +2)*b

Multiply through by 12 to eliminate all denominators, then factor and simplify terms. This reduces to a quadratic equation in terms of b for each fixed a:

3(k-2)b² + 3(-k+4)b - a(a+1)[(k-2)a -k +5] = 0

For each a, we can treat this as a standard Ax² + Bx + C = 0 quadratic equation, where:

• A = 3(k-2)
• B = 3(-k+4)
• C = -a(a+1)[(k-2)a -k +5]

To find integer b values:

1. Calculate the discriminant D = B² - 4AC (must be non-negative and a perfect square for integer roots).
2. Use the quadratic formula to solve for b, then check if the result is an integer within your [2, 1500] range.

When k=2, the quadratic terms vanish, leaving a simple linear equation: b = a(a+1)/2. We'll handle this separately to avoid division-by-zero errors.

Here's the rewritten code that applies all these optimizations. It cuts iterations from 750k to just 498 (one loop over a), which will drastically speed up your search:

import math

def find_solutions(k):
    solutions = []
    max_a = 500
    min_b, max_b = 2, 1500

    # Special case: k=2 simplifies to a linear equation
    if k == 2:
        for a in range(2, max_a + 1):
            a_product = a * (a + 1)
            if a_product % 2 != 0:
                continue
            b = a_product // 2
            if min_b <= b <= max_b:
                # Calculate result with integer arithmetic to avoid float errors
                result = b * (b + 1) // 2
                solutions.append((k, a, b, result))
        return solutions

    # General case: k != 2, use quadratic formula
    A = 3 * (k - 2)
    B = 3 * (-k + 4)

    for a in range(2, max_a + 1):
        a_product = a * (a + 1)
        term = (k - 2) * a - k + 5
        left_value = a_product * term
        C = -left_value

        # Calculate discriminant
        D = B**2 - 4 * A * C
        if D < 0:
            continue  # No real roots, skip this a

        # Check if discriminant is a perfect square
        sqrt_D = math.isqrt(D)
        if sqrt_D * sqrt_D != D:
            continue

        # Solve for b (only positive root matters here)
        numerator_b = -B + sqrt_D
        denominator_b = 2 * A

        if numerator_b % denominator_b != 0:
            continue
        b = numerator_b // denominator_b

        # Verify b is within the required range
        if min_b <= b <= max_b:
            # Compute result with integer arithmetic
            result = ((k - 2) * b * b + (-k + 4) * b) // 2
            solutions.append((k, a, b, result))

    return solutions

# Replace with your actual k value
k_value = 3  # Example: set your k here
results = find_solutions(k_value)
for res in results:
    print(f"{res[0]} {res[1]} {res[2]} {res[3]}")

• Reduced Iterations: From 750,000 to 498 iterations (a ~1500x speedup).
• Integer Arithmetic: Eliminates floating-point operations, which are slower and prone to precision errors.
• Direct Root Calculation: Instead of checking every b, we only compute valid integer b values for each a.

You can further optimize by calculating an upper bound for a based on max_b (since the left side grows cubically with a, while the right side grows quadratically with b), but even without this, the code will be drastically faster than your original approach.

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