No.2324 Two Countries within UEC
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 135
作問者 : sepa38 / テスター : phocom dyktr_06
タグ : / 解いたユーザー数 135
作問者 : sepa38 / テスター : phocom dyktr_06
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。