102126: [AtCoder]ABC212 G - Power Pair
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Score : $600$ points
Problem Statement
Given is a prime number $P$.
How many pairs of integers $(x, y)$ satisfy the following conditions?
- $0 \leq x \leq P-1$
- $0 \leq y \leq P-1$
- There exists a positive integer $n$ such that $x^n \equiv y \pmod{P}$.
Since the answer may be enormous, print it modulo $998244353$.
Constraints
- $2 \leq P \leq 10^{12}$
- $P$ is a prime number.
Input
Input is given from Standard Input in the following format:
$P$
Output
Print the answer modulo $998244353$.
Sample Input 1
3
Sample Output 1
4
Four pairs $(x, y) = (0, 0), (1, 1), (2, 1), (2, 2)$ satisfy the conditions.
Sample Input 2
11
Sample Output 2
64
Sample Input 3
998244353
Sample Output 3
329133417
Input
题意翻译
给定质数 $P$,求有多少个整数 $x,y$,满足 - $0\le x,y\le P-1$ - $\exist n\in \mathbb{N},x^n\equiv y\pmod p$ translated by @ternary_treeOutput
分数:600分
问题描述
给定一个质数P。
满足以下条件的整数对(x, y)有多少个?
- $0 \leq x \leq P-1$
- $0 \leq y \leq P-1$
- 存在一个正整数n,使得$x^n \equiv y \pmod{P}$。
由于答案可能非常大,请对998244353取模后输出。
约束
- $2 \leq P \leq 10^{12}$
- $P$是一个质数。
输入
输入通过标准输入给出以下格式:
$P$
输出
对998244353取模后输出答案。
样例输入1
3
样例输出1
4
有四对满足条件的(x, y):(0, 0), (1, 1), (2, 1), (2, 2)。
样例输入2
11
样例输出2
64
样例输入3
998244353
样例输出3
329133417