Can anyone please explain their solution to SQRGOOD problem from JAN long.
I tried using inclusion-enclusion and binary search but was able to do only 1st subtask.
Thanks
Can anyone please explain their solution to SQRGOOD problem from JAN long.
I tried using inclusion-enclusion and binary search but was able to do only 1st subtask.
Thanks
approach that worked for me (broad strokes):
given n, you can guess z, so that your guess will be not further than \Delta = 10^6 from the answer
compute f(z) - number of x \in [1..z], such that x can be simplified
for every x \in [z-\Delta~..~z+\Delta] determine if x can be simplified
move your guess towards the real answer using information from steps 2 and 3
some details:
you can do some experiments and figure out that guess z = a \cdot n will work, a \approx 2.5505460967303765
to compute f(z) letâ€™s define another function g(z, Y) - number of x \in [1..z], such that x is divisible by some y^2~|~y \in Y, then f(z)=g(z,P), where P is set of all prime numbers from [1..\sqrt{z}], also g is recursive function:
first difficulty is that there are lot of prime numbers under \sqrt{z}, so I ended up implementing segmented bit-packed sieve of Eratosthenes with factorization wheel mod 30, it gives you the way to iterate over prime numbers from P very fast (in case you donâ€™t want to store them), so I split set of primes to two subsets P_{small} \subset [1..\sqrt[3]{z}] and P_{big} \subset (\sqrt[3]{z}..\sqrt{z}] and I handled them differently (you can optimize out divisions and cache some stuff for P_{big}, also you donâ€™t need to store them), and you will need to store P_{small}
second difficulty is computing g(z,P_{small}) (required for g(z,P)) reasonably fast, some caching techniques worked for me
Iâ€™ll try (full disclosure: I only got 50 in the contest, but I looked at a couple of the 7* 100pt answers to see what I missed).
Before starting, I would google â€ścounting square-free numbersâ€ť. There is a fair amount of theory that you probably donâ€™t need to develop from scratch.
The high-level approach is to develop a sufficiently efficient function, say S(x), which will return the number of Square-Free integers less than or equal to x. We then create a new function H(x) = x - S(x) which gives us the number of â€śsimplfyable radicalsâ€ť less than or equal to x. Finally, we implement some sort of search (e.g. binary search, root solving, etc.) to repeatedly evaluate H(x) and find the value of x for which H(x) = N and H(x-1) = N-1. One thing that helps here is that H(x) is monotonic and is very well approximated by (1-6/\pi^2)x, so we can use this fact to get â€ścloseâ€ť to the correct answer very quickly (for me, 2 evaluations was generally good enough to get within 100, after which i brute-forces a square free check).
What remains is to develop an efficient implementation of S(x). This is actually a Project Euler question (#193). For the 10^{14} bar, you can pretty naively implement the following formula which you can search up:
Here S(n) is the number of square-free integers less than or equal to n, \lfloor x \rfloor represents the â€śfloorâ€ť of x, or equivalently, the greatest integer less than or equal to x, and \mu(d) represents the Mobius function.
What is the Mobius function, you might ask? Well, the Mobius function \mu(x) is defined as
If you are so motivated, you can actually derive this equation from nothing more than the same inclusion-exclusion arguments you tried earlier. The following link has the derivation in the appendix: https://arxiv.org/pdf/1107.4890.pdf.
In practice, you can use something very similar to a Sieve of Erastothenes to sieve out \mu(d) in near linear time. If you want to precalculate \mu(x) for 1 \le x \le N for some N, I think you pretty much have two choices:
I tried both, and I actually found the first to be a bit faster as it avoided the multiplies, but it may have been an artifiact of my code.
For the 10^{16} bar (and especially the 10^{18} bar), I wasnâ€™t able to just use the naive sieve (perhaps there is a way for 10^{16} if you really spend time optimizing it). The trick is to realize that there is a smarter way to calculate that sum S(n). To that end, we need a key result and than a clever idea to use it:
The key result involves the Mertens function M(x), which is simply the running sum of the mobius function. That is
The number theory result suggests that the Mertens function can be calculated in sub-linear time. There are a couple of approaches, but one recurrence that can be used is
Deriving this is beyond the scope here.
The other key observation is that, in the evaluation of S(n), once d gets large enough (around \sqrt[3]{2n}), the successive terms \lfloor x/d^2 \rfloor will start matching each other. When this happens, it makes sense to evaluate the sum â€śin blocksâ€ť, where
with \lfloor x/(d)^2 \rfloor == \lfloor x/(d+n)^2 \rfloor is instead replaced by
We can also play this same â€śtail trickâ€ť in the evaluation of the Mertens recurrence. Once d gets large enough, \lfloor x/d \rfloor will start to repeat in blocks.
The Mertens recurrence is really the hardest part. I saw some efficient function memorization structures for speeding this up in one of the solutions I looked at.
Anyway, that was longer than I intended to write, but perhaps this gives the gist of the 100 point solutions (at least the two I looked at seemed to utilize this approach).