DMOPC '19 Contest 6 P2 - Grade 10 Math

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Counting is very difficult so Veshy asks you for help. You are given two positive integers, a and b. You want to find the highest power of a, n, that will divide into b!. In other words you want to find the maximum n such that a^n divides into b!.

Input Specification

The input is a single line containing two space-separated integers, a and b in that order. 1<a<b\le10^6

Output Specification

Output on a single line, the number n such that a^n divides into b! and n is the greatest possible.

Sample Input 1

8 849

Sample Output 1


Sample Input 2

2 2020

Sample Output 2



In sample input 1, 8^{281} is the highest power of 8 that can divide into 849!
In sample input 2, 2^{2013} is the highest power of 2 that can divide into 2020!