CBOJ Welcome Contest Problem 4 - Remainder Table


Submit solution

Points: 15 (partial)
Time limit: 1.0s
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 (0i,jN1).

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 (1N105), 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%]

1N1000

All the integers in the array will range from 1 to 103 inclusive.

Subtask 2 [30%]

1N105

All the integers in the array will range from 1 to 103 inclusive.

Subtask 3 [40%]

No additional constraints.

Sample Input

Copy
4
2 5 5 4

Sample Output

Copy
18

Sample Explanation

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

2554
20110
52004
52004
42110

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


Comments

There are no comments at the moment.