CBOJ Welcome Contest Problem 4 - Remainder Table
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≤i,j≤N−1).
To make the checking process easier for Bob, he will simply ask you to output the sum of all N2 cells. Can you do it fast enough?
Input Specification
The first line of the input will contain an integer N (1≤N≤105), indicating the length of the array A.
The next line of the input will contain N integer ranging from 1 to 105 inclusive, denoting the values of the array A.
Output Specification
Output an integer, representing the sum of all N2 cells in the remainder array.
Subtasks
Subtask 1 [30%]
1≤N≤1000
All the integers in the array will range from 1 to 103 inclusive.
Subtask 2 [30%]
1≤N≤105
All the integers in the array will range from 1 to 103 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