g6-09072. 嵌套的代价 未做

第二段程序的循环套了两层：

s = 0
for i = 1 to n:
    for j = 1 to i:  s = s + 1
print(s)

外层循环变量 $i$ 从 $1$ 取到 $n$；$i$ 每取定一个值，内层循环变量 $j$ 就从 $1$ 取到 $i$，内层循环体每圈把 $s$ 增加 $1$。

请同样不运行程序，数出内层循环体总共执行的次数，也就是程序结束时 $s$ 的值，并直接输出它。

这个次数是 $1+2+\cdots +n=\frac{n(n+1)}{2}$。注意 $n$ 翻一倍时它大约涨成四倍——从线性到平方，代价涨得比 $n$ 本身快得多。

一行，一个整数 $n$。

一行，一个整数，表示内层循环体执行的总次数，即程序结束时 $s$ 的值。

4

10

1

1

样例解释：外层只跑一圈，内层也只跑一圈，$s=1$。

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

答案最大约为 $\frac{10^6\times (10^6+1)}{2}\approx 5\times 10^{11}$，超出 32 位整数（int，上限约 $2.1\times 10^9$）的表示范围，请使用 64 位整数（long long）存储与输出。

本题共 $10$ 个测试点，每个测试点 $10$ 分；第 $1$、$2$ 个测试点与样例同规模，第 $10$ 个测试点取到 $n=10^6$。

本章给过一条判定：$n=10^6$ 配 $O(n^2)$ 约 $10^{12}$ 步，必超时——$1$ 秒时限连 $10^9$ 步都勉强。双重循环的总圈数 $1+2+\cdots +n$ 正是平方增长的最小实例：真跑循环在 $n=10^6$ 时约需 $5\times 10^{11}$ 次运算，按每秒 $10^8$ 次的约定要跑几千秒，只能数出来。交卷自查的第三问还提醒：结果会不会溢出？$5\times 10^{11}$ 装不进 int，必须用 long long。