#59 분수 지수

問題を読み込み中...

本文、提出履歴、提出フォームを準備しています。

#59 분수 지수

作問者: Admin

Statement

問題文の言語

소수

M = 998244353

에 대하여 세 정수 $n,p,q$ 가 주어진다.

먼저 음수 지수를 다음과 같이 정의한다. $y \not\equiv 0 \pmod M$ 일 때, $y^{-1}$ 은

yy^{-1} \equiv 1 \pmod M

을 만족하는 유일한 정수이다.

정수 $k$ 에 대하여 $y^k \pmod M$ 는 다음과 같이 정의한다.

y^k = \begin{cases} \underbrace{y \cdot y \cdots y}_{k\text{번}} \pmod M, & k > 0,\\ 1, & k = 0,\\ (y^{-1})^{-k} \pmod M, & k < 0. \end{cases}

정수 $x$ 가 다음 합동식을 만족하면, $x$ 를 $n^{p/q} \pmod M$ 의 가능한 값이라고 하자.

x^q \equiv n^p \pmod M

주어진 $n,p,q$ 에 대하여 가능한 모든 정수 $x$ 의 합을 출력하여라.

단, $x$ 는

1 \le x < M

인 정수로 생각한다.

입력은 다음과 같은 형식으로 주어진다.

$n\ p\ q$

다음 합동식을 만족하는 모든 정수 $x$ 의 합을 출력한다.

x^q \equiv n^p \pmod {998244353}

#	得点	制約
1	100	전체 제약을 만족하는 테스트입니다.

例 1

入力例

2 3 1

出力例

$q=1$ 이므로 $x \equiv 2^3 \pmod {998244353}$ 이다. 따라서 답은 $8$ 이다.

例 2

入力例

2 1 -1

出力例

499122177

$x^{-1} \equiv 2 \pmod {998244353}$ 을 만족하는 $x$ 는 $2$ 의 역원인 $499122177$ 이다.

例 3

入力例

2 1 3

出力例

275347185

$275347185^3 \equiv 2 \pmod {998244353}$ 이다.