1 solutions

  • 0
    @ 2026-9-18 18:34:06

    注意到,对于所有 x≤⌊n+12⌋x \le \lfloor \frac{n + 1}{2} \rfloor 的结点 xx,xx 与 2x2x 间有一条边,而 2x2x 与 22 之间有一条边,因此所有 2∼⌊n+12⌋2 \sim \lfloor \frac{n + 1}{2} \rfloor 范围内的结点连通。而对于 x>⌊n+12⌋x > \lfloor \frac{n + 1}{2} \rfloor 的结点 xx,xx 不与 2∼⌊n+12⌋2 \sim \lfloor \frac{n + 1}{2} \rfloor 中的结点连通当且仅当 xx 为素数。因此整个图仅包含若干个单独的素数结点与一个大的连通块。

    考虑计算不连通的点对之间的贡献。不难发现,只需要求出所有 >⌊n+12⌋> \lfloor \frac{n + 1}{2} \rfloor 的素数的和与平方和。使用 Min_25 筛或分块打表均可。

    Information

    ID
    39
    Time
    2000ms
    Memory
    512MiB
    Difficulty
    (None)
    Tags
    (None)
    # Submissions
    0
    Accepted
    0
    Uploaded By