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