codeforces-scrape

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

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).