1 条题解

  • 0
    @ 2025-10-19 22:11:30

    我们要找的是:k + n² = m²,其中m和n都是非负整数。 整理这个方程: m² - n² = k (m - n)(m + n) = k

    核心思路:枚举k的所有因子对

    对于k的每个因子对(d1, d2),满足d1 × d2 = k,我们可以得到:

    m - n = d1
    
    m + n = d2
    

    解这个方程组:

    m = (d1 + d2) / 2
    
    n = (d2 - d1) / 2
    

    重要条件:

    d1和d2必须同奇偶(这样才能保证m和n是整数)
    
    m和n都必须是非负整数
    
    m²就是我们要找的完全平方数
    

    算法步骤:

    如果k是0,直接输出0(因为0²=0)
    
    枚举|k|的所有因子d(从1到√|k|)
    
    对于每个因子d,考虑四种情况:
    
        (d1, d2) = (d, k/d)
    
        (d1, d2) = (-d, -k/d)
    
        (d1, d2) = (d, -k/d) (当k为负时)
    
        (d1, d2) = (-d, k/d) (当k为负时)
    
    对每种情况检查d1和d2是否同奇偶
    
    如果同奇偶,计算m和n,检查是否都是非负整数
    
    记录所有满足条件的m²中的最小值
    
    • 1

    信息

    ID
    3533
    时间
    3000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者