SCPB - Editorial

PROBLEM LINKS:

practice

contest

Note: submissions are facing internal errors :frowning:

Difficulty:

Medium

Pre-requirements:

Primality Test

Problem:

There are branches numbered from 2 to X. Squirrels lie on the branch numbers from 2 to P.

Squirrels can jump on to multiples of their branch numbers.

Find the highest branch number in the range 2 to X that no squirrel can reach.

2<=P<=X<=109

Explanation:

The required branch number should be the highest number in the range 2 to X and it should not be divisible by any number in the range 2 to P.

Let us decrease X until it is not divisible by any of the numbers in the range 2 to P (or atmost sqrt(X) )

Even though X can be upto 109, this approach works because the prime gap of numbers less than billion doesn’t exceed 300 and we’re gonna factorize no more than 300 numbers in total. Therefore the complexity is 300*sqrt(109)

Authors Solution:

can be found here