Hi, Codeforces! I have 13 successful hacks of problem D on last round, and also my solution are TLed(probably on one of my tests :)), and i am going to show you, how does it work.

So we have two part of solution.

Now we will try to adjust numbers $$$c, d, x$$$ to hack $$$O(t\sqrt{x} \log x + N \log \log N)$$$ solution. Because we are counting distinct prime factors of numbers like $$$\frac{\frac{x}{d_x} + d}{c}$$$, we will use $$$c = 1$$$. And we are factorizing $$$x$$$. So the first idea is to find $$$x$$$ with biggest divisors number, and that $$$x$$$ is $$$8648640$$$. And then we will try to maximize

where $$$s(n)$$$ -- sum of powers of primes in factorization of $$$n$$$(exactly that much operations we do).

And we have first powerful hack. 10000 tests with $$$c=1, d=x=8648640$$$. List of successful hacks using this method below

But some solutions hadn't hacked by this test. And there are more reasons of it. Sometimes people precalculate lowest divisors powered to its power, and by Second Merten's Theorem it is $$$O(\log \log x)$$$ average, and also our $$$d$$$ approach doesn't work. But the main reason is memory and cache, so we can use randomized generator with more numbers with huge amount of divisors. But how can we use randomized generator on codeforces? It is simple, we just need to set seed in mt19937 and try to adjust it.

Some examples

User: haruki_K

Submission: 110353111

So, there're a lot possibilities to hack solutions, such like use number $$$d = 3 \cdot 5 \cdot 7 \cdot 11 \ldots - x$$$. But there are more stranger things. For example three submissions(all of them is my code of this problem, and all same): 110370237, 110420633, 110439475

If you can explain time difference, you're welcome.

So in summary, I want to say, that constaints was quite inbalanced, because people who just hadn't precalculated answer, but figured out idea just got TL or hacked solution and negative delta and it is bad.

Also i want to thank plagues just for sending my solution to try to mock me :)