問題一覧 > 通常問題

No.2649 [Cherry 6th Tune C] Anthem Flower

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 125
作問者 : 👑 Kazun / テスター : 👑 p-adic
0 ProblemId : 4793 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-02-23 21:36:36

ストーリー

チェリーちゃんを含めた MM 人は NN 日間花を咲かせる努力をしました. その結果, k (1kN)k~(1 \leq k \leq N) 日目には kk 輪の花を咲かせることができました.

つまり, NN 日間で合計 k=1Nk\displaystyle \sum_{k=1}^N k 輪の花を咲かせました.

問題文

k=1Nk\displaystyle \sum_{k=1}^N kMM で割った余りを求めよ.

TT 個のテストケースについて答えよ.

制約

  • 1T2×1051 \leq T \leq 2 \times 10^5
  • 各テストケースに対する制約
    • 1N<104×1061 \leq N \lt 10^{4 \times 10^6}.
    • 1M1091 \leq M \leq 10^9
  • テストファイルに関する制約
    • TT 個のテストケースにおける NN桁数の総和は 4×1064 \times 10^6 以下である.

入力

TT
Testcase1{\rm Testcase}_1
Testcase2{\rm Testcase}_2
\vdots
TestcaseT{\rm Testcase}_T
NN MM

出力

出力は TT 行からなる. 第 t (1tT)t~(1 \leq t \leq T) 行目には, 第 tt テストケースに対する解答を整数で出力せよ.

最後に改行を忘れないこと.

サンプル

サンプル1
入力
3
3 100
5 10
123456789012345678901234567890 20240223
出力
6
5
1774557

  • [第 11 テストケース] k=13k=1+2+3=6\displaystyle \sum_{k=1}^3 k=1+2+3=6100100 で割った余りは 66 である.
  • [第 22 テストケース] k=15k=1+2+3+4+5=15\displaystyle \sum_{k=1}^5 k=1+2+3+4+5=151010 で割った余りは 55 である.
  • [第 33 テストケース] NN は非常に大きい可能性がある.

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