問題一覧 > 通常問題

No.1926 Sequence of Remainders

レベル : / AI推定難易度 : 725 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 157
作問者 : ripity / テスター : 👑 qand
お気に入りにしたユーザー ProblemId : 7825 / 自分の提出
問題文最終更新日: 2022-05-02 22:03:07
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 342 (順位表) の他の問題:

Problem Statement

Define an integer sequence $a=(a_0,a_1,\dots,a_N)$ of length $N+1$ as follows. Note that the indices start from $0$.

$a_i = \left\{ \begin{array}{ll} K \% M & (i = 0)\\ a_{i-1} \% (M-i) & (0 \lt i\le N) \end{array} \right.$
Here, for a non-negative integer $x$ and a positive integer $y$, $x\% y$ denotes the remainder when $x$ is divided by $y$.
Find $a_N$.

Answer $T$ test cases for $1$ input file.

Input

The input is given in the following format.
Line $1$ contains an integer $T$ representing the number of test cases, and each of the following $T$ lines contains a test case. 
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Each test case is given in the following format. 
$N\ M\ K$

  • $1\le T\le 10^5$
  • $1\le N\lt M\le 10^9$
  • $1\le K\le 10^9$
  • All input values are integers.

Output

Print $T$ lines in total. On the $i$-th line, print the answer to $\mathrm{case}_i$.

Sample

Sample 1
Input
4
1 6 34
2 3 16
51492374 82390104 791314957
22775420 93039351 628500036
Output
4
0
0
70263930

  • In test case $1$, $a_0=34 \% 6=4,\ a_1=4 \% 5=4$.
  • In test case $2$, $a_0=16 \% 3=1,\ a_1=1 \% 2=1,\ a_2=1 \% 1=0$.

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