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\times2\times\cdots\times849. Every two numbers in the expansion of 849!=1\times2\times3\cdots 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+\cdots+\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.

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


Comments

There are no comments at the moment.