問題一覧 > 通常問題

No.2324 Two Countries within UEC

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 138
作問者 : sepa38sepa38 / テスター : phocomphocom dyktr_06dyktr_06
0 ProblemId : 9549 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-05-23 18:38:15

問題文

セパ国には $N$ 個、やきとり国には $M$ 個の町があります。 セパ国の町は $1, 2, \cdots , N$ 、やきとり国の町は $1, 2, \cdots , M$ の番号がつけられており、 セパ国の町 $x$ と やきとり国の町 $y$ の親交度は $x \times y \mod P$ です。

$Q$ 個のクエリが与えられるので、$i$ 番目のクエリでは、セパ国の町 $x_i$ と親交度が $f_i$ である やきとり国の町の個数を出力してください。

入力

$N \ M \ P \ Q$
$x_1\ f_1$
$x_2\ f_2$
$\ \ \ \ \vdots$
$x_Q\ f_Q$

制約

  • $1 \leq N, M \leq 10^9$
  • $2 \leq P \leq 10^9$
  • $1 \leq Q \leq 10^5$
  • $1 \leq x_i \leq N$
  • $0 \leq f_i \leq P - 1$
  • $P$ は素数
  • 入力はすべて整数

出力

$i$ 行目に $i$ 番目のクエリの答えを出力してください。

サンプル

サンプル1
入力
5 5 11 3
2 8
4 7
5 3
出力
1
0
1

セパ国の町 $2$ と親交度が $8$ である町はやきとり国の町 $4$ のみなので $1$ 、$\\$ セパ国の町 $4$ と親交度が $7$ である町はやきとり国に存在しないので $0$ 、$\\$ セパ国の町 $5$ と親交度が $3$ である町はやきとり国の町 $5$ のみなので $1$ を出力します。

サンプル2
入力
85 82 17 8
55 1
23 2
31 7
83 0
8 0
76 16
32 1
14 1
出力
5
5
5
4
4
5
5
5

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