1 条题解

  • 0
    @ 2025-10-27 22:54:18

    首先对这个式子变一下形:

    1u+1v=1f\frac{1}{u}+\frac{1}{v}=\frac{1}{f} fu+fv=uvfu+fv=uv v(uf)=fuv(u-f)=fu v=fuufv=\frac{fu}{u-f}

    然后我们发现分母太复杂了,将其换元,设 k=ufk=u-f ,即 u=k+fu=k+f

    然后式子可以改写为:

    v=f(k+f)k=f+f2kv=\frac{f(k+f)}{k}=f+\frac{f^2}{k}

    然后因为 vv 是正整数,所以式子的另一边也得是正整数,所以对于一个数 ff,它的解数就是 f2f^2 的因数个数,然后我们设 f2f^2kk 个因数,那么解数就是 $\left \lceil \frac{k}{2} \right \rceil=\frac{2k+1}{2}$

    f(x)f(x) 表示 xx 因数个数,注意到 f(x)f(x) 是积性函数,然后由唯一分解定理:f=i=1mpicif=\prod_{i=1}^{m} p_i^{c_i} ,则有:

    f(x2)=i=1m2ci+1f(x^2)=\prod_{i=1}^{m} 2c_i+1

    发现当 R=230R=2^{30} 的时候答案可以用__int128存,然后 100100 以内的所有质数乘起来要小于这个数,所以使用DFS

    然后写几个剪枝:

    1.首先对于每一个 cic_i 单调不增,因为我们交换两个 cic_iRR 是没有影响的,又因为要答案最小所以要单调不增

    2.最优性剪枝

    • 1

    信息

    ID
    521
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    35
    已通过
    7
    上传者