No.1926 Sequence of Remainders
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 150
作問者 :
ripity
/ テスター :
遭難者
タグ : / 解いたユーザー数 150
作問者 :
ripity
/ テスター :
遭難者
問題文最終更新日: 2022-05-02 22:03:07
問題文
長さ $N+1$ の整数列 $a=(a_0,a_1,\dots,a_N)$ を以下で定めます。添え字が $0$ から始まることに注意してください。
ここで、非負整数 $x$ と 正整数 $y$ に対して、$x\% y$ は $x$ を $y$ で割ったあまりを表します。$a_i = \left\{ \begin{array}{ll} K \% M & (i = 0)\\ a_{i-1} \% (M-i) & (0 \lt i\le N) \end{array} \right.$
$a_N$ を求めてください。
$1$ つの入力ファイルにつき $T$ 個のテストケースに答えてください。
入力
入力は以下の形式からなる。$1$ 行目ではテストケースの個数を表す整数 $T$ が与えられ、続く $T$ 行にわたってそれぞれテストケースが与えられる。
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
各テストケースは以下の形式で与えられる。
$N\ M\ K$
- $1\le T\le 10^5$
- $1\le N\lt M\le 10^9$
- $1\le K\le 10^9$
- 入力はすべて整数
出力
合計 $T$ 行出力してください。$i$ 行目には $\mathrm{case}_i$ の答えを出力してください。
サンプル
サンプル1
入力
4 1 6 34 2 3 16 51492374 82390104 791314957 22775420 93039351 628500036
出力
4 0 0 70263930
- $1$ 個目のテストケースについて、$a_0=34 \% 6=4,\ a_1=4 \% 5=4$ です。
- $2$ 個目のテストケースについて、$a_0=16 \% 3=1,\ a_1=1 \% 2=1,\ a_2=1 \% 1=0$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。