## Editorial for DMOPC '19 Contest 6 P2 - Grade 10 Math

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Tzak

Let  and  be the list of prime factors and the list of their respective frequencies in the prime factorization of  . The elements of  can be obtained through prime factorizing  . Now, for each  in  , we find  : the greatest integer value that  can be multiplied by, and remain not greater than the number of times  appears in the prime factorization of  . The answer is the minimum over all  .

For example, consider Sample Input 1, with  ,  . After prime factorizing,  and  . Now consider how many times  occurs in the expansion of  . Every two numbers in the expansion of  have  as a factor, and there are  such numbers. However, for elements which are divisible by  in the expansion, there is still one  which we have not yet considered. Similarly, there are  such elements. For elements which are divisible by  , there is yet one more  which we have not considered, and the pattern continues. We will find that in total, there are  occurrences of  in the prime factorization of  . Now, we find  , which is  . Since there is only one such  , this is our answer.

Note:  means  , rounded down to the nearest integer.

Pseudocode:

read a, b

(prime factorize a)

for i in [2, sqrt(a)]
if a is divisible by i
append i to A
while a is divisible by i
a /= i
cnt[i]++

if a != 1
insert a into A
cnt[a]++

(find all n_i)

n = MAXIMUM_VALUE
for A_i in A
occurrences = 0
looking_for = A_i
while b / looking_for != 0
occurrences += b / looking_for
looking_for *= A_i
n_i = occurrences / cnt[A_i]
n = min(n, n_i)

print n

Time complexity:  