409608: GYM103643 K Cards

Goma has asked Peach to play a little game. Goma has put $$$N$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$) face up cards in a circle labeled $$$1$$$ to $$$N$$$ clockwise where the $$$i$$$th card has the number $$$a_i$$$ on it ($$$1 \leq a_i \leq 10^9$$$). Goma simply tells Peach to pick a number $$$k$$$ from $$$1$$$ to $$$N$$$ inclusive, and to take a sum of the cards in the following fashion: To begin, flip the first card face down. Then go $$$k$$$ cards clockwise and if the card is face up, flip it face down and continue the process, otherwise stop. Then take the sum of all the face down cards. Peach is curious and would like to know what sum they would get for each $$$k$$$ from $$$1$$$ to $$$N$$$.

The first line contains $$$N$$$.

The next line contains $$$N$$$ integers denoting $$$a_1, a_2,...,a_N$$$.

Test case 1 is the sample and will not be worth points.

Test case 2-4: $$$N \leq 1000$$$

Test cases 5-21: No further constraints

Output $$$N$$$ lines, where the $$$i$$$th line is the resulting sum when Goma chooses $$$k = i$$$.

5
1 2 3 4 5

15
15
15
15
1

If $$$k = 2$$$, and $$$N = 5$$$, Peach would flip the 1st card face down, then the 3rd, then the 5th, then the 2nd, then the 4th, then stop since the 1st card is already face down. Since all the cards are face down the sum we get is $$$1 + 2 + 3 + 4 + 5 = 15$$$.

$$$---------------------------------------------$$$

Problem Idea: Bossologist

Problem Preparation: Bossologist

Occurrences: Intermediate 8, Advanced 6