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 A and cnt be the list of prime factors and the list of their respective frequencies in the prime factorization of a. The elements of A can be obtained through prime factorizing a. Now, for each A_i in A, we find n_i: the greatest integer value that cnt_i can be multiplied by, and remain not greater than the number of times A_i appears in the prime factorization of b!. The answer is the minimum over all n_i.

For example, consider Sample Input 1, with a = 8, b = 849. After prime factorizing, A = [2] and cnt = [3]. Now consider how many times 2 occurs in the expansion of 849! = 1 \times 2 \times \dots \times 849. Every two numbers in the expansion of 849! = 1 \times 2 \times \dots have 2 as a factor, and there are \lfloor\frac{849}{2}\rfloor = 424 such numbers. However, for elements which are divisible by 2^2 = 4 in the expansion, there is still one 2 which we have not yet considered. Similarly, there are \lfloor\frac{849}{4}\rfloor = 212 such elements. For elements which are divisible by 2^3 = 8, there is yet one more 2 which we have not considered, and the pattern continues. We will find that in total, there are \lfloor\frac{849}{2}\rfloor+\lfloor\frac{849}{4}\rfloor+\lfloor\frac{849}{8}\rfloor+\lfloor\frac{849}{16}\rfloor+\dots+\lfloor\frac{849}{512}\rfloor = 424+212+106+53+26+13+6+3+1 = 844 occurrences of 2 in the prime factorization of 849!. Now, we find n_i, which is \lfloor\frac{844}{3}\rfloor = 241. Since there is only one such n_i, this is our answer.

Note: \lfloor x \rfloor means x, rounded down to the nearest integer.


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

if a != 1
    insert a into A

(find all n_i)

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: \mathcal O(\sqrt{n}+\frac{\log^2 n}{\log \log n})


There are no comments at the moment.