← 返回题目列表

AtCoder · KeioPC2025_a

A. 我喜欢MST问题

中文机器翻译题面 查看原题

配点 : 100 点

問題文

在顶部 编号为 1 减去 N 有 N 頂点 0 边的图。你是 对 k = 1,2,\dots , N-1 执行以下操作:

  • 2 顶点 选择 u, v 并在它们之间绘制一条边。该操作的成本是 设其为除以 (u + v) \times k 该值应乘以 N 后的余数。 当

但是, 运算前设定中包含的N-1 操作完成时,必须连接图形。 求

N-1 操作的最小可能总成本。 您将获得

T 测试用例,因此请解决每个测试用例。

制約

  • 1 \le T \le 100
  • 2 \le N \le 10^9
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出。 打印

N

出力

T 行。i 在线 \mathrm{case}_i 的答案。 对于第


入力例 1

3
4
56
789

出力例 1

1
0
130

1 个测试用例,总成本可以计算如下: 选择 1 。 对于

  • k = 1 什么时候 u = 1, v = 4 。成本是 (1 + 4) \times 1 \bmod 4 = 1
  • k = 2 什么时候 u = 2, v = 4 。成本是 (2 + 4) \times 2 \bmod 4 = 0
  • k = 3 什么时候 u = 1, v = 3 。成本是 (1 + 3) \times 3 \bmod 4 = 0

这是一种操作图的方法,使其在最后成为连通的,总成本为 0 没有以下内容,所以答案是 1 。