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

For example, consider Sample Input 1, with a=8a=8, b=849b=849. After prime factorizing, A=[2]A=[2] and cnt=[3]cnt=[3]. Now consider how many times 22 occurs in the expansion of 849!=1\times2\times\cdots\times849849!=1\times2\times\cdots\times849. Every two numbers in the expansion of 849!=1\times2\times3\cdots849!=1\times2\times3\cdots have 22 as a factor, and there are \lfloor\frac{849}{2}\rfloor=424\lfloor\frac{849}{2}\rfloor=424 such numbers. However, for elements which are divisible by 2^2=42^2=4 in the expansion, there is still one 22 which we have not yet considered. Similarly, there are \lfloor\frac{849}{4}\rfloor=212\lfloor\frac{849}{4}\rfloor=212 such elements. For elements which are divisible by 2^3=82^3=8, there is yet one more 22 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\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 22 in the prime factorization of 849!849!. Now, we find n_in_i, which is \lfloor\frac{844}{3}\rfloor=241\lfloor\frac{844}{3}\rfloor=241. Since there is only one such n_in_i, this is our answer.

Note: \lfloor x\rfloor\lfloor x\rfloor means xx, 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})\mathcal O(\sqrt{n}+\frac{\log^2n}{\log \log n})


Comments

There are no comments at the moment.