CBOJ Welcome Contest Problem 4 - Remainder Table


Submit solution

Points: 15 (partial)
Time limit: 1.5s
Memory limit: 128M

Author:
Problem type

We've all heard of the times table, but what about the remainder table?

Similar to the times table, the remainder table is a table used to define the modulo operator. The cell at \((i, j)\) will be equal to i % j.

Bob wants to test your knowledge on the remainder table! He has given you an array of \(N\) positive integers \(A\). Instead of i % j, he will ask you to get the value of A[i] % A[j], where \((0 \le i, j \le N - 1)\).

To make the checking process easier for Bob, he will simply ask you to output the sum of all \(N^2\) cells. Can you do it fast enough?

Input Specification

The first line of the input will contain an integer \(N\) \((1 \le N \le 10^5)\), indicating the length of the array \(A\).

The next line of the input will contain \(N\) integer ranging from \(1\) to \(10^5\) inclusive, denoting the values of the array \(A\).

Output Specification

Output an integer, representing the sum of all \(N^2\) cells in the remainder array.

Subtasks

Subtask 1 [30%]

\(1 \le N \le 1000\)

All the integers in the array will range from \(1\) to \(10^3\) inclusive.

Subtask 2 [30%]

\(1 \le N \le 10^5\)

All the integers in the array will range from \(1\) to \(10^3\) inclusive.

Subtask 3 [40%]

No additional constraints.

Sample Input

4
2 5 5 4

Sample Output

18

Sample Explanation

The table of remainder for \([2, 5, 5, 4]\) is as follows:

\(2\)\(5\)\(5\)\(4\)
\(2\)\(0\)\(1\)\(1\)\(0\)
\(5\)\(2\)\(0\)\(0\)\(4\)
\(5\)\(2\)\(0\)\(0\)\(4\)
\(4\)\(2\)\(1\)\(1\)\(0\)

The sum of \(1 + 1 + 2 + 4 + 2 + 4 + 2 + 1 + 1\) is equal to \(18\).


Comments

There are no comments at the moment.