問題一覧 > 通常問題

No.1803 Remainder of Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 47
作問者 : NatsubiSoganNatsubiSogan / テスター : noko_utnoko_ut nok0nok0 penguinmanpenguinman
5 ProblemId : 7514 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-21 12:52:50

問題文

数列 $A=(1,2,\dots,N)$ があります。あなたは、以下の一連の操作を、$A$ の要素数が $2$ 以上である間繰り返します。

  • $A$ の要素を $1$ つ選ぶ。これを $x$ とする。
  • $x$ 以外の $A$ の要素を $1$ つ選ぶ。これを $y$ とする。
  • コスト $(x+y) \bmod M$ を支払って、$y$ を $A$ から削除する。

あなたは、支払うコストの合計を最小化したいと思っています。

$T$ 個のテストケースが与えられるので、それぞれについてコストの最小値を求めてください。

入力

入力の $1$ 行目に、テストケースの数 $T$ が以下の形式で与えられる。

$T$

そして、$T$ 個のテストケースが続く。これらはそれぞれ以下の形式で与えられる。

$N$ $M$
  • 入力はすべて整数
  • $1 \leq T \leq 10^5$
  • $2 \leq N \leq 10^9$
  • $1 \leq M \leq 2N$

出力

$T$ 行出力してください。

$i \ (1 \leq i \leq T)$ 行目には、$i$ 番目のテストケースについて、コストの合計の最小値を出力してください。

最後に改行してください。

サンプル

サンプル1
入力
1
3 2
出力
1

はじめ、$A=(1,2,3)$ です。以下のようにして、合計コスト $1$ を達成できます。

  • $x=1,\ y=3$ とする。コスト $(1+3) \bmod 2 = 0$ を支払い、$y \ (=3)$ を $A$ から削除する。$A=(1,2)$ となる。
  • $x=1,\ y=2$ とする。コスト $(1+2) \bmod 2 = 1$ を支払い、$y \ (=2)$ を $A$ から削除する。$A=(1)$ となり、操作は終了になる。

コストを $0$ にする操作手順は存在しないので、$1$ が答えとなります。

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