AT_jsc2023_final_c.Power Convergence

给定一个整数 $N$。

对于正整数 $x$，定义 $f(x)$ 如下：

• 考虑满足 $x^k \equiv x^{k+1} \bmod N$ 的非负整数 $k$。如果存在这样的 $k$，则 $f(x)$ 为满足条件的最小 $k$；若不存在，则 $f(x)=0$。

请计算 $\sum_{1 \leq x \leq N} f(x)$ 的值。

对于一个输入文件中的所有 $T$ 个测试用例，请分别作答。

输入由标准输入以以下格式给出。

$T\ case_1\ case_2\ \cdots\ case_T$

每个测试用例 $case_i$ 的格式如下：

$N$

输出 $T$ 行，第 $i$ 行输出对应 $case_i$ 的答案。

样例解释 1

例如 $N=4$ 时，$f(x)$ 的值如下所示：

• $f(1)=0\ \ \ \ $（$1^0 \equiv 1^1 \bmod 4$）
• $f(2)=2\ \ \ \ $（$2^2 \equiv 2^3 \bmod 4$）
• $f(3)=0\ \ \ \ $（不存在满足 $3^k \equiv 3^{k+1} \bmod 4$ 的 $k$）
• $f(4)=1\ \ \ \ $（$4^1 \equiv 4^2 \bmod 4$）

所以答案为 $0+2+0+1=3$。

数据范围

• $1 \leq T \leq 10$
• $2 \leq N \leq 10^9$
• 输入的值均为整数。

由 ChatGPT 5 翻译