## 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: