1114C.md (2077B)
1 Source: https://codeforces.com/problemset/problem/1114/C 2 3 C. Trailing Loves (or L'oeufs?) 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 standard input 16 17 output 18 19 standard output 20 21 The number "zero" is called "love" (or "l'oeuf" to be precise, literally means "egg" in French), for example when denoting the zero score in a game of tennis. 22 23 Aki is fond of numbers, especially those with trailing zeros. For example, the number $9200$ has two trailing zeros. Aki thinks the more trailing zero digits a number has, the prettier it is. 24 25 However, Aki believes, that the number of trailing zeros of a number is not static, but depends on the base (radix) it is represented in. Thus, he considers a few scenarios with some numbers and bases. And now, since the numbers he used become quite bizarre, he asks you to help him to calculate the beauty of these numbers. 26 27 Given two integers $n$ and $b$ (in decimal notation), your task is to calculate the number of trailing zero digits in the $b$-ary (in the base/radix of $b$) representation of $n\,!$ ([factorial](https://en.wikipedia.org/wiki/Factorial) of $n$). 28 29 Input 30 31 The only line of the input contains two integers $n$ and $b$ ($1 \le n \le 10^{18}$, $2 \le b \le 10^{12}$). 32 33 Output 34 35 Print an only integer — the number of trailing zero digits in the $b$-ary representation of $n!$ 36 37 Examples 38 39 Input 40 41 ``` 42 6 9 43 ``` 44 45 Output 46 47 ``` 48 1 49 ``` 50 51 Input 52 53 ``` 54 38 11 55 ``` 56 57 Output 58 59 ``` 60 3 61 ``` 62 63 Input 64 65 ``` 66 5 2 67 ``` 68 69 Output 70 71 ``` 72 3 73 ``` 74 75 Input 76 77 ``` 78 5 10 79 ``` 80 81 Output 82 83 ``` 84 1 85 ``` 86 87 Note 88 89 In the first example, $6!_{(10)} = 720_{(10)} = 880_{(9)}$. 90 91 In the third and fourth example, $5!_{(10)} = 120_{(10)} = 1111000_{(2)}$. 92 93 The representation of the number $x$ in the $b$-ary base is $d_1, d_2, \ldots, d_k$ if $x = d_1 b^{k - 1} + d_2 b^{k - 2} + \ldots + d_k b^0$, where $d_i$ are integers and $0 \le d_i \le b - 1$. For example, the number $720$ from the first example is represented as $880_{(9)}$ since $720 = 8 \cdot 9^2 + 8 \cdot 9 + 0 \cdot 1$. 94 95 You can read more about bases [here](https://en.wikipedia.org/wiki/Radix).