SQRGOOD - Editorial

melfice · January 16, 2018, 8:10am

PROBLEM LINK:

Practice
Contest

Author: Tiny Wong
Tester: Alexey Zayakin
Editorialist: Oleksandr Kulkov

DIFFICULTY:

HARD

PREREQUISITES:

Dirichlet convolution, number theory

PROBLEM:

You’re given number n. You have to find n^{th} not square-free number.

QUICK EXPLANATION:

Solution is complicated and comes into three separate steps. First you make a guess at point \dfrac{n}{1-\tfrac{6}{\pi^2}}. That will give you error of up to 10^6 elements. After that you will have segment [L;R] on which you will search for this number. To do this you will have to calculate amount of square-good numbers before L in O(n^{2/5}), which is the first step. After that you try every element in [L;R] and check if it’s square-good in O(n^{1/3} \log \log n) overall using sieve.

EXPLANATION:

Initial guess

If we denote Q(x) as number of square-free integers between 1 and x, then it holds that

Q(x) = \dfrac{x}{\zeta(2)}+O(\sqrt{x})

Here \zeta(2) = \dfrac{\pi^2}{6} is value of Riemann zeta function. Under Riemann hypothesis which tends to be true it can be reduced to

Q(x) = \dfrac{6x}{\pi^2}+O\left(x^{17/54 + \varepsilon}\right)

which is close to 5 \cdot 10^5 for x \approx 10^{18}. Now we should find such number k that

k-Q(k)\approx n \to k \approx n + \dfrac{6k}{\pi^2} \to k \approx \dfrac{n}{1-\tfrac{6}{\pi^2}}

This will make the initial guess and give us some [L;R] segment to search for exact answer.

Calculating square-free numbers up to L in O(n^{2/5})

Let’s learn to count square-free numbers up to some number n in fastest way.

The very natural sieve-like solution is to cross-out each number of kind p^2 for every prime number p. We are only interested in p \leq \sqrt n so why not just subtract from n all numbers that are divisible by p^2? In this case we will subtract some numbers twice, for example if we subtracted numbers divisible by 2^2 and 3^2, we subtracted numbers divisible by 6^2 for each of them. Now we can add back numbers divisible by squares of two distinct prime numbers but then we will add numbers divisible by squares of three prime numbers once again. Do you recognize it yet? Yep, that’s inclusion-exclusion principle. You can write this approach as the following sum:

S(n) = \sum\limits_{d=1}^{\sqrt n} \mu(d) \left\lfloor \dfrac{n}{d^2} \right \rfloor

Here \mu(d) is Möbius function which equals 0 for non square-free numbers and (-1)^m for numbers d=p_1 p_2 \dots p_m. This allows you to calculate S(n) in O(\sqrt n). We need to improve that. If you take d \geq \sqrt[3]{n} there will be only O(\sqrt[3]{n}) possible values of \left\lfloor\dfrac{n}{d^2} \right\rfloor. Let’s try to split our sum in two parts and sum up first one by d in S_1(n) and second one by \left\lfloor\dfrac{n}{d^2} \right\rfloor in S_2(n). Let k \approx \sqrt[3]{n}.
Let’s find numbers d_1, d_2 such that semi-segment (d_1, d_2] is the same segment numbers from which have \left\lfloor \dfrac n {d^2} \right \rfloor=k. For these numbers we have:

\dfrac{n}{d_1^2} \geq k + 1 \to d_1 \leq \sqrt{\dfrac{n}{k+1}} \to d_1 = \left\lfloor \sqrt{\dfrac{n}{k+1}}\right\rfloor

\dfrac{n}{d_2^2} \geq k \to d_2 \leq \sqrt{\dfrac{n}{k}} \to d_2 = \left\lfloor\sqrt{\dfrac{n}{k}} \right\rfloor

Let’s denote x_i = \left\lfloor \sqrt{\dfrac n i} \right\rfloor. Then we can write

S_2(n) = \sum\limits_{i=1}^k i \sum\limits_{j=x_{i+1} + 1}^{x_i} \mu(j)

Now let’s denote Mertens function as M(n) = \sum\limits_{i=1}^n \mu(i). Then we can write it as

S_2(n) = \sum\limits_{i=1}^k i \cdot [M(x_i) - M(x_{i+1})]

First sum will be easier to calculate since it’s just S_1(n) = \sum\limits_{d=1}^{x_{k+1}}\mu(d) \left\lfloor \dfrac{n}{d^2} \right \rfloor and can be calculated in O(x_{k+1}).

How fast can we calculate Mertens function for particular variable n? We should use trick from this codeforces article. It implies that M(n) = 1 - \sum\limits_{k=1}^n M\left(\left\lfloor \dfrac{n}{k}\right\rfloor\right). Given that \left\lfloor\dfrac{\lfloor \tfrac a b \rfloor}{c}\right\rfloor=\left\lfloor\dfrac{a}{bc} \right\rfloor we can assure that we only need values of Mertens function in points of form \left\lfloor \dfrac{n}{k}\right\rfloor, i.e. only O(\sqrt n) distinct points. If you will compute these values from smallest to largest, it will require from you at most \sum\limits_{i=1}^{\sqrt n} O(\sqrt i)\approx \int\limits_0^{\sqrt n} \sqrt x dx = O(n^{3/4}) when you consider numbers which are less then \sqrt n and \sum\limits_{i=1}^{\sqrt n} O\left(\sqrt{\dfrac n i}\right)=O(n^{3/4}) when larger numbers are considered. If you will compute first O(K) values of Mertens function beforehand using linear sieve, it will be even possible to lower the complexity per query to O\left(\tfrac{n}{\sqrt K}\right) which is also described in that article!

So you can calculate M(x_i) in O(n^{1/2} i^{-1/2} K^{-1/2}), thus calculating S_2 in

\sum \limits_{i=1}^k O(n^{1/2}i^{-1/2}K^{-1/2})=O(n^{1/2}k^{1/2}K^{-1/2})

It will be minimum over K if

K=n^{1/2}k^{1/2}K^{-1/2} \to K^{3/2}=n^{1/2}k^{1/2} \to K = n^{1/3}k^{1/3}

thus S_2 is calculated in O(n^{1/3}k^{1/3}).

Overall complexity for calculating S(n) hence will be O(x_k+n^{1/3}k^{1/3})=O(n^{1/2}k^{-1/2}+n^{1/3}k^{1/3}). It will have minimum in case

n^{1/2-1/3}=k^{1/2+1/3} \to k^{5/6}=n^{1/6} \to k = n^{1/5}

and will be equal to O(n^{1/3+1/15})=O(n^{2/5}). Thus you’ll have to take K=O(n^{2/5}) and k=O(n^{1/5}) for this complexity.

Checking for each number in [L;R] if it’s square-free

Here is the easiest part of solution. Once you have segment in which you will search, you’ll have to check each number if it’s square-free or not. If number m is not square-free then either there exists prime number p \leq m^{1/3} such that p^2 divides m or it has only one prime factor q which is greater than n^{1/3} and q^2 divides m. Solution comes in four steps.

Find all primes less or equal n^{1/3}.
Take an array c_{L..R} with initial value c_i=i.
For each prime p sieve its multiples in [L;R] once and check if they’re divided by p^2. In any case divide c_{k \cdot p} by p.
Now in c_i there are only factors of i that are greater then n^{1/3}. We just have to check whether c_i is perfect square now.

That will allow you to check all the numbers if they’re square-free in O(n^{1/3} \log \log n) and finish off the problem.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.