codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1091C.md (2256B)


      1 Source: https://codeforces.com/problemset/problem/1091/C
      2 
      3 C. New Year and the Sphere Transmission
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 There are $n$ people sitting in a circle, numbered from $1$ to $n$ in the order in which they are seated. That is, for all $i$ from $1$ to $n-1$, the people with id $i$ and $i+1$ are adjacent. People with id $n$ and $1$ are adjacent as well.
     22 
     23 The person with id $1$ initially has a ball. He picks a positive integer $k$ at most $n$, and passes the ball to his $k$-th neighbour in the direction of increasing ids, that person passes the ball to his $k$-th neighbour in the same direction, and so on until the person with the id $1$ gets the ball back. When he gets it back, people do not pass the ball any more.
     24 
     25 For instance, if $n = 6$ and $k = 4$, the ball is passed in order $[1, 5, 3, 1]$.
     26 
     27 Consider the set of all people that touched the ball. The fun value of the game is the sum of the ids of people that touched it. In the above example, the fun value would be $1 + 5 + 3 = 9$.
     28 
     29 Find and report the set of possible fun values for all choices of positive integer $k$. It can be shown that under the constraints of the problem, the ball always gets back to the $1$-st player after finitely many steps, and there are no more than $10^5$ possible fun values for given $n$.
     30 
     31 Input
     32 
     33 The only line consists of a single integer $n$ ($2 \leq n \leq 10^9$) — the number of people playing with the ball.
     34 
     35 Output
     36 
     37 Suppose the set of all fun values is $f_1, f_2, \dots, f_m$.
     38 
     39 Output a single line containing $m$ space separated integers $f_1$ through $f_m$ in increasing order.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 6
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 1 5 9 21
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 16
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 1 10 28 64 136
     65 ```
     66 
     67 Note
     68 
     69 In the first sample, we've already shown that picking $k = 4$ yields fun value $9$, as does $k = 2$. Picking $k = 6$ results in fun value of $1$. For $k = 3$ we get fun value $5$ and with $k = 1$ or $k = 5$ we get $21$.
     70 
     71  ![](https://espresso.codeforces.com/8dc54b5b4be6ed15f622635f7d8663d22b40c2a2.png) 
     72 
     73 In the second sample, the values $1$, $10$, $28$, $64$ and $136$ are achieved for instance for $k = 16$, $8$, $4$, $10$ and $11$, respectively.