E - Sequence of Multiples

コンテスト時間: 2022-02-13(日) 12:00 ~ 2022-02-13(日) 14:00 (120分) AtCoderホームへ戻る

E - Sequence of Multiples 解説

実行時間制限: 6 sec / メモリ制限: 1024 MB

配点 : $800$ 点

整数 $N, X$ が与えられます。整数列 $A = (A_1, \ldots, A_N)$ が次の条件をすべて満たすとします。

$\sum_{i=1}^N A_i$ として考えられる最小値を、 $998244353$ で割った余りを求めてください。

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

入力は以下の形式で標準入力から与えられます。

 $T$ 
 $\text{case}_1$ 
 $\vdots$ 
 $\text{case}_T$

各テストケースは以下の形式で与えられます。

 $N$   $X$

$T$ 行出力してください。 $i$ 行目には、 $\text{case}_i$ に対する答えを出力してください。

Copy

5
5 100
1 10
10 1
1000000000000000000 1
100 100

Copy

はじめの $3$ つのテストケースについて、例えば次の $A$ が $\sum_{i=1}^N A_i$ の最小値を与えます：

Score : $800$ points

You are given integers $N$ and $X$ . Assume that an integer sequence $A = (A_1, \ldots, A_N)$ satisfies all of the conditions below.

Find the minimum possible value of $\sum_{i=1}^N A_i$ , modulo $998244353$ .

There are $T$ test cases, each of which should be solved.

Input is given from Standard Input from the following format:

 $T$ 
 $\text{case}_1$ 
 $\vdots$ 
 $\text{case}_T$

Each case is in the following format:

 $N$   $X$

Print $T$ lines. The $i$ -th line should contain the answer for $\text{case}_i$ .

Copy

5
5 100
1 10
10 1
1000000000000000000 1
100 100

Copy

Here is a sequence $A$ that minimizes $\sum_{i=1}^N A_i$ for each of the first three test cases.