注意到,对于所有 x≤⌊n+12⌋x \le \lfloor \frac{n + 1}{2} \rfloorx≤⌊2n+1⌋ 的结点 xxx,xxx 与 2x2x2x 间有一条边,而 2x2x2x 与 222 之间有一条边,因此所有 2∼⌊n+12⌋2 \sim \lfloor \frac{n + 1}{2} \rfloor2∼⌊2n+1⌋ 范围内的结点连通。而对于 x>⌊n+12⌋x > \lfloor \frac{n + 1}{2} \rfloorx>⌊2n+1⌋ 的结点 xxx,xxx 不与 2∼⌊n+12⌋2 \sim \lfloor \frac{n + 1}{2} \rfloor2∼⌊2n+1⌋ 中的结点连通当且仅当 xxx 为素数。因此整个图仅包含若干个单独的素数结点与一个大的连通块。
考虑计算不连通的点对之间的贡献。不难发现,只需要求出所有 >⌊n+12⌋> \lfloor \frac{n + 1}{2} \rfloor>⌊2n+1⌋ 的素数的和与平方和。使用 Min_25 筛或分块打表均可。
By signing up a Hydro universal account, you can submit code and join discussions in all online judging services provided by us.
Using your Hydro universal account