58B.md (1428B)
1 Source: https://codeforces.com/problemset/problem/58/B 2 3 B. Coins 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 In Berland a money reform is being prepared. New coins are being introduced. After long economic calculations was decided that the most expensive coin should possess the denomination of exactly *n* Berland dollars. Also the following restriction has been introduced for comfort: the denomination of each coin should be divisible by the denomination of any cheaper coin. It is known that among all the possible variants the variant with the largest number of new coins will be chosen. Find this variant. Print in the order of decreasing of the coins' denominations. 22 23 Input 24 25 The first and only line contains an integer *n* (1 ≤ *n* ≤ 106) which represents the denomination of the most expensive coin. 26 27 Output 28 29 Print the denominations of all the coins in the order of decreasing. The number of coins must be the largest possible (with the given denomination *n* of the most expensive coin). Also, the denomination of every coin must be divisible by the denomination of any cheaper coin. Naturally, the denominations of all the coins should be different. If there are several solutins to that problem, print any of them. 30 31 Examples 32 33 Input 34 35 ``` 36 10 37 ``` 38 39 Output 40 41 ``` 42 10 5 1 43 ``` 44 45 Input 46 47 ``` 48 4 49 ``` 50 51 Output 52 53 ``` 54 4 2 1 55 ``` 56 57 Input 58 59 ``` 60 3 61 ``` 62 63 Output 64 65 ``` 66 3 1 67 ```