問題一覧 > 教育的問題

No.3579 Range Product Inverse Image

レベル : / AI推定難易度 : 1250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 22
作問者 : 👑 p-adic
お気に入りにしたユーザー ProblemId : 10523 / 自分の提出
問題文最終更新日: 2026-06-27 14:50:51
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 503 (順位表) の他の問題:

Problem Statement

You are given as input a positive integer $N$, a prime $P$, a non-negative integer $C$, and a sequence $A$ of non-negative integers of length $N$.

 

Find the number of pairs of integers $(\ell,r)$ satisfying $1 \leq \ell \leq r \leq N$ and

$\displaystyle \prod_{i = \ell}^{r} A_i \equiv C \pmod{P} $

.

Here, for each positive integer $i$ not exceeding $N$, $A_i$ denotes the $i$-th element of $A$. ($A = (A_1,\ldots,A_N)$)

Input

The input is given from standard input in $2$ lines in the following format:

  • The $1$st line contains $N, P, C$, separated by single spaces.
  • The $2$nd line contains $A_i$ for each positive integer $i$ not exceeding $N$, in increasing order of $i$, separated by single spaces.
$N$ $P$ $C$
$A_1$ $\cdots$ $A_N$

Constraints

The input satisfies the following constraints:

  • $N$ is an integer satisfying $1 \leq N \leq 10^5$.
  • $P$ is a prime satisfying $1 \leq P \leq 10^9$.
  • $C$ is an integer satisfying $0 \leq C < P$.
  • For every positive integer $i$ not exceeding $N$, $A_i$ is an integer satisfying $0 \leq A_i < P$.

Output

Print the number of pairs of integers $(\ell,r)$ satisfying the conditions on $1$ line.

Print a newline at the end.

Sample

Sample 1
Input
1 2 0
0
Output
1

We have $(N,P,C) = (1,2,0)$ and $A = (0)$. The only pair of integers $(\ell,r)$ satisfying $1 \leq \ell \leq r \leq N$ is $(1,1)$, and

$\displaystyle \prod_{i=1}^{1} A_i = A_1 = 0 \textcolor{blue}{\equiv} C \pmod{P} $

holds.

Sample 2
Input
2 2 1
1 1
Output
3

We have $(N,P,C) = (2,2,1)$ and $A = (1,1)$. There are $3$ pairs of integers $(\ell,r)$ satisfying $1 \leq \ell \leq r \leq N$, namely $(1,1),(1,2),(2,2)$, and

$\displaystyle \begin{array}{rcccl} \displaystyle \prod_{i=1}^{1} A_i &\displaystyle = &\displaystyle A_1 &\displaystyle = &\displaystyle 1 &\displaystyle \textcolor{blue}{\equiv} &\displaystyle C \pmod{P} \\ \displaystyle \prod_{i=1}^{2} A_i &\displaystyle = &\displaystyle A_1 A_2 &\displaystyle = &\displaystyle 1 &\displaystyle \textcolor{blue}{\equiv} &\displaystyle C \pmod{P} \\ \displaystyle \prod_{i=2}^{2} A_i &\displaystyle = &\displaystyle A_2 &\displaystyle = &\displaystyle 1 &\displaystyle \textcolor{blue}{\equiv} &\displaystyle C \pmod{P} \end{array} $

hold.

Sample 3
Input
2 2 0
1 0
Output
2

We have $(N,P,C) = (2,2,0)$ and $A = (1,0)$. There are $3$ pairs of integers $(\ell,r)$ satisfying $1 \leq \ell \leq r \leq N$, namely $(1,1),(1,2),(2,2)$, and

$\displaystyle \begin{array}{rcccl} \displaystyle \prod_{i=1}^{1} A_i &\displaystyle = &\displaystyle A_1 &\displaystyle = &\displaystyle 1 &\displaystyle \textcolor{red}{\not\equiv} &\displaystyle C \pmod{P} \\ \displaystyle \prod_{i=1}^{2} A_i &\displaystyle = &\displaystyle A_1 A_2 &\displaystyle = &\displaystyle 0 &\displaystyle \textcolor{blue}{\equiv} &\displaystyle C \pmod{P} \\ \displaystyle \prod_{i=2}^{2} A_i &\displaystyle = &\displaystyle A_2 &\displaystyle = &\displaystyle 0 &\displaystyle \textcolor{blue}{\equiv} &\displaystyle C \pmod{P} \end{array} $

hold.

Sample 4
Input
2 3 1
2 2
Output
1

We have $(N,P,C) = (2,3,1)$ and $A = (2,2)$. There are $3$ pairs of integers $(\ell,r)$ satisfying $1 \leq \ell \leq r \leq N$, namely $(1,1),(1,2),(2,2)$, and

$\displaystyle \begin{array}{rcccl} \displaystyle \prod_{i=1}^{1} A_i &\displaystyle = &\displaystyle A_1 &\displaystyle = &\displaystyle 2 &\displaystyle \textcolor{red}{\not\equiv} &\displaystyle C \pmod{P} \\ \displaystyle \prod_{i=1}^{2} A_i &\displaystyle = &\displaystyle A_1 A_2 &\displaystyle = &\displaystyle 4 &\displaystyle \textcolor{blue}{\equiv} &\displaystyle C \pmod{P} \\ \displaystyle \prod_{i=2}^{2} A_i &\displaystyle = &\displaystyle A_2 &\displaystyle = &\displaystyle 2 &\displaystyle \textcolor{red}{\not\equiv} &\displaystyle C \pmod{P} \end{array} $

hold.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。