← 返回题目列表

Codeforces · 1553/F

F. 成对模

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

您有一个数组 $$$a$$$,由 $$$n$$$ 不同的正整数组成,编号从 $$$1$$$ 到 $$$n$$$。将 $$$p_k$$$ 定义为 $$$$$$p_k = \sum_{1 \le i, j \le k} a_i \bmod a_j,$$$$$$ 其中 $$$x \bmod y$$$ 表示 $$$x$$$ 除以 $$$y$$$ 所得的余数。您必须找到并打印 $$$p_1, p_2, \ldots, p_n$$$。

输入

第一行包含 $$$n$$$ — 数组的长度 ($$$2 \le n \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 空格分隔的不同整数 $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 3 \cdot 10^5$$$, $$$a_i \neq a_j$$$ if $$$i \neq j$$$)。

输出

打印 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$。

示例

输入 #1

4
6 2 7 3

输出 #1

0 2 12 22

输入 #2

3
3 2 1

输出 #2

0 3 5