Rope skipping

View as PDF

Submit solution

Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

During recess, a group of ~n~ students go outside for rope skipping. Each turn, two of the students will turn the rope, and one student jumps. The two rope turners will hold two ends of the rope, one spinning clockwise, the other counter-clockwise, so that the rope periodically hits the ground, and passes over the skipper's head. The skipper stands in between the two rope turners, and must jump when the rope hits the ground. If the rope hits the skipper's leg, the skipper loses.

All ~n~ students are very strong and flexible, their flexibility are ~c_1, c_2, \ldots, c_n~.

If the ~i~-th student is the skipper, then for ~c_i~ seconds, their feet will be on the ground. Afterwards, they jump, and their feet will be off the ground for the next ~c_i~ seconds. This process repeats. For example, if ~c_i = 3~:

  • On seconds ~1, 2, 3~ their feet is on the ground.

  • On seconds ~4, 5, 6~ their feet is off the ground.

  • On seconds ~7, 8, 9~ their feet is on the ground.

  • On seconds ~10, 11, 12~ their feet is off the ground.

  • ~\ldots~

If the ~u~-th and ~v~-th students are chosen to be the rope turners, then the rope hits the ground at precisely the seconds that are multiples of ~gcd(c_u, c_v)~, in which ~gcd(x, y)~ denotes the greatest common divisor of two positive integers ~x~ and ~y~. For example, if ~c_u = 6~ and ~c_v = 8~, ~gcd(6, 8) = 2~, therefore the rope will hit the ground at seconds ~2, 4, 6, 8, 10, \ldots~

You are given the flexibility of all ~n~ students. For the ~i~-th student, calculate how many pairs of students ~u~ and ~v~ (~u < v~), such that if the ~i~-th student is the skipper, then they will never lose.

Input

The first line contains a single integer ~n~ (~3 \le n \le 10^6~), the number of students.

The second line contains ~n~ integers ~c_1, c_2, \ldots, c_n~ (~1 \le c_i \le 10^6~), the flexibility of the ~n~ students.

Output

Output ~n~ integers, the ~i~-th of which is the number of pairs of students such that if the ~i~-th student is the skipper, they will never lose.

Scoring

  • Subtask 1 (~65~ points): ~n \le 100~

  • Subtask 2 (~65~ points): No additional constraints

The total score for this problem is ~130~.

Sample Input 1

3
1 6 8

Sample Output 1

1 0 0

Sample Input 2

12
1 2 3 4 5 6 7 8 9 10 11 12

Sample Output 2

15 3 1 0 0 0 0 0 0 0 0 0

Notes

In the first example:

  • If the first student is the skipper, their feet do not touch the ground at seconds ~2, 4, 6, 8, \ldots~ because ~c_1 = 1~. The rope turners may be the second and third student, due to ~c_2 = 6, c_3 = 8~, ~gcd(6, 8) = 2~, and the moments that the rope touches the ground are seconds ~2, 4, 6, 8, \ldots~.

  • If the second student is the skipper, they'd lose if the other two were the rope turners, because ~gcd(1, 8) = 1~, thus the rope touches the ground at every integer seconds. The same thing happens if the third student is the skipper

Fun fact: The game described in the statement is more similar to Double Dutch than Skipping rope, but played with a single rope.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.