Editorial for COCI '11 Contest 4 #5 Broj

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.

To solve this for large values of $P$ ~P~ we will use a modification of the sieve of Eratosthenes. The size of our sieve will be $10^9/P$ ~10^9/P~. Integers in the sieve represent multiples of $P$ ~P~. During the execution of this algorithm, we can find the smallest prime factors or mark only multiples of prime numbers smaller than $P$ ~P~.

For smaller values of $P$ ~P~ we can binary search through $[1, 10^9/P]$ ~[1, 10^9/P]~, again looking at these numbers as the corresponding multiples of $P$ ~P~. For some number, we must find the number of integers not greater and relatively prime with that number. We can do this by using the inclusion-exclusion principle with prime numbers less than $P$ ~P~.

With careful implementation, this solution can work for much larger values of $P$ ~P~ than requested for this subtask.

We can also solve this task for smaller values of $P$ ~P~ by making use of the periodic behaviour of the smallest prime factors. Let $A(n)$ ~A(n)~ be the smallest prime factor of $n$ ~n~, $B(k)$ ~B(k)~ the $k^\text{th}$ ~k^\text{th}~ prime number, and $T(k)$ ~T(k)~ the product of the first $k$ ~k~ primes. For $A(n) \le B(k)$ ~A(n) \le B(k)~, $A(n+T(k)) = A(n)$ ~A(n+T(k)) = A(n)~ holds. So it's enough to know $A(n)$ ~A(n)~ for $n \le T(k)$ ~n \le T(k)~ in order to find the $N^\text{th}$ ~N^\text{th}~ prime whose smallest prime factor is $B(k)$ ~B(k)~.

Comments

There are no comments at the moment.