AT_abc212_g [ABC212G] Power Pair
题目描述
给定一个素数 $P$。
有多少对整数 $(x,\ y)$ 满足以下条件？
- $0 \leq x \leq P-1$
- $0 \leq y \leq P-1$
- 存在某个正整数 $n$，使得 $x^n \equiv y \pmod{P}$
由于答案可能非常大，请输出答案对 $998244353$ 取模后的结果。
输入格式
输入以以下格式从标准输入给出。
> $P$
输出格式
请输出答案对 $998244353$ 取模后的结果。
说明/提示
## 限制条件
- $2 \leq P \leq 10^{12}$
- $P$ 是素数
## 样例解释 1
满足条件的 $4$ 组为 $(x,\ y) = (0,\ 0),\ (1,\ 1),\ (2,\ 1),\ (2,\ 2)$。
由 ChatGPT 4.1 翻译