102457: [AtCoder]ABC245 Ex - Product Modulo 2
Description
Score : $600$ points
Problem Statement
Among the sequences of length $K$ consisting of integers, $A=(A_1, \ldots, A_K)$, how many satisfy all of the conditions below?
Find the count modulo $998244353$.
-
$0\leq A_i \leq M-1$ for every $i(1\leq i\leq K)$.
-
$\displaystyle\prod_{i=1}^{K} A_i \equiv N \pmod M$.
Constraints
- $1 \leq K \leq 10^9$
- $0 \leq N \lt M \leq 10^{12}$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$K$ $N$ $M$
Output
Print the answer.
Sample Input 1
2 3 6
Sample Output 1
5
The five sequences $A$ satisfying the conditions are $(1,3),(3,1),(3,3),(3,5),(5,3)$.
Sample Input 2
10 0 2
Sample Output 2
1023
Sample Input 3
1000000000 20220326 1000000000000
Sample Output 3
561382653
Be sure to find the count modulo $998244353$.
Input
题意翻译
- 求有多少个长为 $k$，值域为 $[0,m-1]$ 的序列 $a$ 满足 $\prod_{i=1}^ka_i\equiv n\pmod m$。 - $1\le k\le10^9$，$0\le n<m\le10^{12}$，答案对 $998244353$ 取模。Output
问题描述
在由整数组成的长度为$K$的序列$A=(A_1, \ldots, A_K)$中，有多少个满足以下所有条件？
找到答案对$998244353$取模的结果。
-
对于所有$i(1\leq i\leq K)$，都有$0\leq A_i \leq M-1$。
-
$\displaystyle\prod_{i=1}^{K} A_i \equiv N \pmod M$。
限制条件
- $1 \leq K \leq 10^9$
- $0 \leq N \lt M \leq 10^{12}$
- 输入中的所有值都是整数。
输入
输入以以下格式从标准输入给出：
$K$ $N$ $M$
输出
打印答案。
样例输入1
2 3 6
样例输出1
5
满足条件的五个序列$A$是$(1,3),(3,1),(3,3),(3,5),(5,3)$。
样例输入2
10 0 2
样例输出2
1023
样例输入3
1000000000 20220326 1000000000000
样例输出3
561382653
确保找到对$998244353$取模的答案。