問題一覧 > 通常問題

No.1926 Sequence of Remainders

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 114
作問者 : ripityripity / テスター : 遭難者遭難者
1 ProblemId : 7825 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-02 22:03:07

問題文

長さ $N+1$ の整数列 $a=(a_0,a_1,\dots,a_N)$ を以下で定めます。添え字が $0$ から始まることに注意してください。

$a_i = \left\{ \begin{array}{ll} K \% M & (i = 0)\\ a_{i-1} \% (M-i) & (0 \lt i\le N) \end{array} \right.$
ここで、非負整数 $x$ と 正整数 $y$ に対して、$x\% y$ は $x$ を $y$ で割ったあまりを表します。
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。