贡献名单

想法	标程	数据	验题	题解
035966_L3			irris	035966_L3

题目背景

提示：题目描述最后附有一份简洁题意。

题外话：CCF 的 F 是 Federation，不是 Foundation。

---

$2035$ 年 $10$ 月 $24$ 日，为了响应国家号召，促进区域 OI 水平均衡发展，时任 GZCF（Guizhou Computer Federation，贵州省计算机协会）主任 strcmp（下称「小 W」） 和时任 CQCF（Chongqing Computer Federation，重庆市计算机协会）主任 CQYC_ZJYjoe（下称「小 Z」） 达成秘密协议：从重庆市抽调一批 OIers 移民到贵州省，路费等由小 Z 承担，但小 W 需要安排好 TA 们的住所。

题目描述

根据小 Z 的要求，小 W 一共要盖 $n$ 座楼房。为了更符合重庆人的品味（？），这些楼房需要「错落有致」：具体来说，第 $i$ 座楼房的层高应为 $i$ 米，且楼高 $h_i=s_i \times i$ 米单调不降（即 $h_i \ge h_{i-1}$）。当然，每座楼房的楼层数 $s_i$ 应为正整数。

与此同时，小 W 已经找到了一座层高为 $1$，楼层数 $s_1=a$ 的烂尾楼（$h_1=a$），并决定将它作为第 $1$ 座楼房。

为了避免小 Z 反悔，小 W 决定尽快完工，因此他这么盖楼：

• 在所有使得 $h_2 =2 \times s_2\ge h_1$ 的 $s_2$ 中，取最小值作为 $s_2$，即 $s_2=\lceil\dfrac{h_1}{2}\rceil$；
• 在所有使得 $h_3 =3 \times s_3\ge h_2$ 的 $s_3$ 中，取最小值作为 $s_3$，即 $s_3=\lceil\dfrac{h_2}{3}\rceil$；
• 在所有使得 $h_4 =4 \times s_4\ge h_3$ 的 $s_4$ 中，取最小值作为 $s_4$，即 $s_4=\lceil\dfrac{h_3}{4}\rceil$；
• ……
• 在所有使得 $h_i =i \times s_i\ge h_{i-1}$ 的 $s_i$ 中，取最小值作为 $s_i$，即 $s_i=\lceil\dfrac{h_{i-1}}{i}\rceil$；
• ……
• 在所有使得 $h_n =n \times s_n\ge h_{n-1}$ 的 $s_n$ 中，取最小值作为 $s_n$，即 $s_n=\lceil\dfrac{h_{n-1}}{n}\rceil$。

当然，小 W 最关注的并不是这个，而是另外一件事情——他前一天成功忽悠了 CCF 主席，双方达成协议：每盖楼 $1$ 米（烂尾楼的高度也算盖楼的高度），CCF 补贴给小 W $1$ 万元钱（即 CCF 补贴给小 W $h_1+h_2+\ldots+h_n$ 万元钱）。

他想知道：此时 CCF 会补贴给他多少万元钱？

---

给定两个正整数 $n,a$。

现有两个正整数数列 $\{h_n\},\{s_n\}$ 和一个正整数 $W$，满足：

$$\begin{cases} s_1=a, \\ s_i=\lceil \dfrac{h_{i-1}}{i} \rceil, \\ h_i=i \times s_i,\\ W=h_1+h_2+\ldots+h_n. \end{cases} $$

试计算 $W$ 的值。

输入格式

本题有多组数据。

第一行，一个正整数 $T$，表示数据组数。

下面 $T$ 行，每行两个整数 $n,a$。

输出格式

$T$ 行，每行一个整数，对应一组数据的答案。

样例 #1

样例输入 #1

7
1 1
2 4
3 9
10 6
23 44
108 301
9181918 918918

样例输出 #1

1
8
31
116
2077
114514
45568273044922784

提示

样例解释：

• 对于第 $1$ 组数据，$s$ 数列为 $\{1\}$，$h$ 数列为 $\{1\}$，故答案为 $1$。
• 对于第 $2$ 组数据，$s$ 数列为 $\{4,2\}$，$h$ 数列为 $\{4,4\}$，故答案为 $8$。
• 对于第 $3$ 组数据，$s$ 数列为 $\{9,5,4\}$，$h$ 数列为 $\{9,10,12\}$，故答案为 $31$。

---

测试点编号	$n \le$	$a \le$	分值
$1$	$100$	$1000$	$40$
$2$	$10^7$		$30$
$3$		$10^6$

对于 $100\%$ 的数据，$1 \le T \le 10^5$，$1 \le n \le 10^7$，$1 \le a \le 10^6$。