You are not logged in. Please login at www.codechef.com to post your questions!

×

KOL16C - Editorial

PROBLEM LINK:

Practice
Contest

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:

  1. 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.

  2. 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.

asked 30 Oct '17, 17:00

meooow's gravatar image

6★meooow ♦
7.3k720
accept rate: 48%

edited 13 Nov '17, 23:59

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,359
×1,056
×100
×6

question asked: 30 Oct '17, 17:00

question was seen: 359 times

last updated: 13 Nov '17, 23:59