2169D2 - Removal of a Sequence (Hard Version)

Here is an implementation of $$$O(\sqrt{A} \cdot \log{A})$$$ (where $$$A = 10^{12}$$$) solution from the beginning of editorial for this problem: 349377703.

It works in $$$10.5$$$ seconds on current testset and was intended to be too slow to pass: the expected complexity is $$$O(\sqrt{A})$$$.

But after some optimizations I was able to speed it up x6.5 times down to $$$1.64$$$ seconds and get AC: 349377750

Optimizations are:

• Usage of reciprocal multiplication for division on $$$y$$$

• Usage of reciprocal multiplication for division on small (up to $$$2^{21}$$$) numbers

• If-else checking for very small (up to $$$3$$$) result of division

Can someone hack it? Or maybe speed it up even more?