PROBLEM LINK:
Editorialist: Soumik Sarkar
DIFFICULTY:
HARD
PREREQUISITES:
Basic maths, Binary search
PROBLEM:
Given a set of factorials of consecutive numbers F, a set of consecutive prime numbers P and an integer t, the task is to find out how many of the numbers in F contain at least one of the prime numbers from set P exactly t times.
QUICK EXPLANATION:
For each prime p_i in P separately calculate the contiguous range where each number has exactly t occurrences of p_i in its factorial. Calculate the size of the intersection of the given range F with the union of all these ranges.
EXPLANATION:
The first step is to precompute the maximum required number of primes (3 \cdot 10^6) using a sieve such as the Sieve of Eratosthenes. Then let us consider the problem without the F, in other words when F = [1.. \infty).
Think of a single prime p. Let cnt_p(n) be the number of times p occurs in n!. To find this value, observe that all multiples of p which are \le n each contribute one p. But each multiple of p^2 contributes an extra p. This extends to higher powers of p also. So cnt_p(n) = \lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + ... + \lfloor n/p^x \rfloor where x is the highest integer such that \lfloor n/p^x \rfloor \ne 0.
Observe that cnt_p(n) is a non-decreasing function of n. So there will be some range of values (possibly empty) where cnt_p(n) for each value will be t. So we can binary search on n to find the first such value. It is easy to see that this first value must be a multiple of p, and the range will extend until the next multiple of p. This saves us one binary search for the upper bound.
So for each prime p_i, we can find a range [L_i..R_i] where cnt_{p_i}(n) = t for each L_i \le n \le R_i. However, we need only the part of these ranges that lie in the given range F. So let us replace each such range with the intersection of itself and F. The problem states that one or more primes can occur in the factorial t times. Hence the size of the union of the ranges corresponding to each prime is the answer. Any standard algorithm can be used to find the union.
Optimizations:
-
Important: When t < p_i then L_i is simply p_i \cdot t. Since maximum t is 3 \cdot 10^5, the binary search is needed in the worst case only for primes \le 3 \cdot 10^5, which is \approx 0.87 \% of the first 3 \cdot 10^6 primes. So for \approx 99.13 \% of primes we can get L_i in constant time.
-
It is also possible to compute the union of the ranges along with the main iteration over the primes. This is because if p_i < p_j then L_i < L_j and R_i < R_j, so the ranges will be obtained in sorted order.
Let the maximum value in F be N and the maximum size of P be M. Each cnt_p(n) takes \mathcal{O}(\log N). So each binary search takes \mathcal{O}(\log^2 N). There will be M binary searches, so the total complexity is \mathcal{O}(M \log^2 N).
However, since for \approx 99 \% of primes there is no binary search, the complexity is basically \mathcal{O}(M).
ALTERNATIVE SOLUTION:
Feel free to share any alternative solution below.
EDITORIALIST’S SOLUTION:
Editorialist’s solution can be found here.