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$$$ 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
