Part 1

先来模拟一下样例第 $4$ 组数据，答案为 $116$：

$\color{blue}i$	$\color{blue}1$	$\color{blue}2$	$\color{blue}3$	$\color{blue}4$	$\color{blue}5$	$\color{blue}6$	$\color{blue}7$	$\color{blue}8$	$\color{blue}9$	$\color{blue}10$
$s_i$	$6$	$3$	$\color{red}2$
$h_i$		$6$		$8$	$10$	$12$	$14$	$16$	$18$	$20$

再来模拟一下样例第 $5$ 组数据，答案为 $2077$：

$\color{blue}i$	$\color{blue}1$	$\color{blue}2$	$\color{blue}3$	$\color{blue}4$	$\color{blue}5$	$\color{blue}6$	$\color{blue}7$	$\color{blue}8$	$\color{blue}9$	$\color{blue}10$	$\color{blue}11$	$\color{blue}12$	$\color{blue}13$	$\color{blue}14$	$\color{blue}15$	$\color{blue}16$	$\color{blue}17$	$\color{blue}18$	$\color{blue}19$	$\color{blue}20$	$\color{blue}21$	$\color{blue}22$	$\color{blue}23$
$s_i$	$44$	$22$	$15$	$12$	$10$	$9$	$8$	$\color{red}7$
$h_i$		$44$	$45$	$48$	$50$	$54$	$56$		$63$	$70$	$77$	$84$	$91$	$98$	$105$	$112$	$119$	$126$	$133$	$140$	$147$	$154$	$161$

Part 2

不难发现，当 $s_i \le i$ 时，$s_i$ 便不再变化了。

证明：

若 $s_i \le i$，则：

$$h_i=i \times s_i$$ $$\dfrac{h_{i}}{i+1}=\dfrac{i \times s_i}{i+1}$$

---

$$s_i \le i$$ $$s_i-i-1 \le -1$$ $$s_i-i-1<0$$

---

$$s_i = \dfrac{i \times s_i + s_i}{i+1} > \dfrac{i \times s_i}{i+1}>\dfrac{i \times s_i+s_i-i-1}{i+1}=s_i-1 $$$$s_i>\dfrac{i \times s_i}{i+1}>s_i-1$$ $$s_i>\dfrac{h_{i}}{i+1}>s_i-1$$ $$\lceil \dfrac{h_{i}}{i+1} \rceil=s_i$$ $$s_{i+1}=s_i$$

故 $s_i$ 不再变化。

Part 3

此外，当这个时刻到来时，$i \le \sqrt{2a}$。

证明：

$s_i \le i$ 等价于 $h_i \le i^2$。设 $f(i)=h_i$，$g(i)=i^2$，$d(i)=f(i)-g(i)$，则 $f(1)=a$，$g(1)=1$，$d(1)=a-1$，$s_i \le i$ 等价于 $d(i)\le0$；

当 $i$ 增加 $1$（即设 $j=i+1$）时，$g(j)-g(i)=2j-1$；

显然：

$$\lceil \dfrac{h_{i}}{j} \rceil-\dfrac{h_{i}}{j}<1$$ $$\lceil \dfrac{h_{j-1}}{j} \rceil \times j-\dfrac{h_{i}}{j} \times j<j $$$$h_j-h_i<j$$ $$f(j)-f(i)<j$$ $$f(j)-f(i)\le j-1$$

故 $d(j)-d(i)=[f(j)-g(j)]-[f(i)-g(i)]=[f(j)-f(i)]-[g(j)-g(i)]\le (j-1)-(2j-1)=-j$，即 $d(j)-d(i)\le-j$。

也就是说，当 $i$ 增加到 $j=i+1$ 时，$d$ 函数的值至少减小 $j$；

当 $i=\sqrt{2a}$ 时，$d(i)=a-1-2-3-\ldots-\sqrt{2a}=a-\dfrac{(1+\sqrt{2a})\times \sqrt{2a}}{2}=-\sqrt{\dfrac{a}{2}}<0$，显然这个时刻已经到来。

Part 4

于是，我们暴力计算 $h_1 \sim h_{\sqrt{2a}}$，剩下的是等差数列，套公式就行了。

最终的时间复杂度为 $O(T\sqrt{a})$，空间复杂度为 $O(1)$。

Part 5

std：

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int T;
    cin >> T;
    while (T--)
    {
        long long n, a, i;
        cin >> n >> a;
        long long w = a;
	    for (i = 2; i <= n; i++)
	    {
		    if (a % i) a += (i - a % i);
		    w += a;
		    if (a / i <= i) break;
	    }
	    if (i < n) w += (n - i) * (a / i * (i + 1) +  a / i * n) / 2;
	    cout << w << endl;
    }
	return 0;
}