← 返回题目列表

AtCoder · arc135_e

E. 倍数序列

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

给你整数 N 和 X。假设一个整数序列 A = (A_1, \ldots, A_N) 满足以下所有条件。

  • A_1 = X.
  • 对于每个 i (1\leq i\leq N), A_i 是的倍数 i.
  • A 正在严格增加。换句话说, A_1 < \cdots < A_N 成立。

找到以下的最小可能值 \sum_{i=1}^N A_i,模数 998244353.

有 T 测试用例,每个测试用例都应该被解决。

约束

  • 1\leq T\leq 10
  • 1\leq N \leq 10^{18}
  • 1\leq X \leq 10^{18}

输入

输入由标准输入按以下格式给出:

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

每个案例的格式如下:

N X

输出

打印 T 行。的 i- 第行应包含以下问题的答案 \text{case}_i.


样本输入 1

5
5 100
1 10
10 1
1000000000000000000 1
100 100

示例输出 1

525
10
55
75433847
61074

这是一个序列 A 最小化 \sum_{i=1}^N A_i 对于前三个测试用例。

  • 第一个测试用例: A = (100, 102, 105, 108, 110).
  • 第二个测试用例: A = (10).
  • 第三个测试用例: A = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10).