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 nondecreasing 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:
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)$. ALTERNATIVE SOLUTION:Feel free to share any alternative solution below. EDITORIALIST'S SOLUTION:Editorialist's solution can be found here. asked 30 Oct '17, 17:00
