1 条题解

  • 0
    @ 2022-11-18 23:07:22

    注意到若 aimodx=mia_i \bmod x = m_i,则说明 aimia_i - m_ixx 的倍数,即 xx 是所有 aimia_i - m_i 的公共因子。

    这说明 xx 是所有差的最大公因数的因子,可以使用 gcd\gcd 计算最大公因数,然后 O(n)O(\sqrt{n}) 的枚举其因数即可。

    另外请注意,aimodx=mia_i \bmod x = m_i 蕴含着 x>mix > m_i,样例中的 11 只是个特例。

    这里是代码

    • 1

    信息

    ID
    63
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    5
    已通过
    4
    上传者