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

So we have two parts of solution.

The first is to precalculate lowest divisor of each number. It can be done with simple Eratosthenes sieve, which has time complexity $$$O(N \log N)$$$ if you do sieve loop for all numbers, and $$$O(N \log \log N)$$$ if you do loop only when number is prime. It can also be done with $$$O(N)$$$ time and memory using linear sieve.

Second part is the answer calculation, you need to add $$$2^k$$$, where $$$k$$$ -- number of different prime divisors. So if you haven't precalucated it on sieve step, it will be $$$O(\log x)$$$ per divisor, otherwise it will be $$$O(1)$$$.

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 is below

https://mirror.codeforces.com/contest/1499/hacks/714784

https://mirror.codeforces.com/contest/1499/hacks/714699

https://mirror.codeforces.com/contest/1499/hacks/714697

https://mirror.codeforces.com/contest/1499/hacks/714692

https://mirror.codeforces.com/contest/1499/hacks/714688

https://mirror.codeforces.com/contest/1499/hacks/714629

https://mirror.codeforces.com/contest/1499/hacks/714683

But some solutions weren'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 problem 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 \dots) - 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 imbalanced, 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. EDUCATIONAL round problems constraints shouldn't be like this.

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