全部评论 6

  • 存在理论更优时间复杂度做法,可做到O(sqrt(n+m)log(n+m)+n{2/3}/log2n)

    33分钟前 来自 山东

    1
    • userId_undefined
      Lost
      回复
      Lost

      呃好像忘加katex了,理论最优时间复杂度应该是 O(n+mlog(n+m)+n23log2n)O(\sqrt{n+m}\log(n+m)+\dfrac{n^{\frac 23}}{\log^2n})

      32分钟前 来自 山东

      1
    • userId_undefined
      Lost
      回复
      Lost

      第二项的n替换为n+m,不过n和m是同一个量级的无所谓就是了

      32分钟前 来自 山东

      1
    • userId_undefined
      cjdst
      回复
      Lost

      这么强?!

      31分钟前 来自 广东

      0
  • 跟团队成员说声对不起,我昨天在没有看清题面和题解的情况下发表了“顶多中位黄”“数据为什么不开满”的言论,请大家不要受误导。由于这题是数论我完全没法评级,只能建议对照洛谷的类似题目评级。如果有人质疑,可以拿比赛时的AC率说话

    2天前 来自 广东

    1
  • 不认为有这么低,比较严谨的证明如下:

    x=i+jx=i+j,所有 i+j=xi+j=x(i,j)(i,j) 的总贡献为:

    f(x)=i=max(1,xm)min(n,x1)C(x2,i1)×C(n+mx,ni)f(x)=\sum_{i=max(1,x-m)}^{min(n,x-1)} C(x-2,i-1)\times C(n+m-x,n-i)

    这正是范德蒙德卷积公式。当你把式子化简,你就会发现这个式子的值与 xx 无关!变成了 C(n+m2,n1)C(n+m-2,n-1)。也就是说对于每个质数带来的贡献都是 C(n+m2,n1)C(n+m-2,n-1)

    分析到这里就豁然开朗,答案为 1n+m1\sim n+m 的质数个数 ×C(n+m2,n1)\times C(n+m-2,n-1)

    综上,可以给到中位绿 \sim 下位蓝 都可以的,欢迎大家评论下方交流。

    2天前 来自 广东

    1
  • 2天前 来自 重庆

    0
  • 抱歉,我昨天看 AKer 的用时较高就误认为是 O(nm)O(nm) 的暴力,但也可能是 O((n+m)log2(n+m))O((n+m)log_2(n+m)) 的质数筛

    2天前 来自 浙江

    0
  • 3天前 来自 浙江

    0

热门讨论