Okay… So I am gonna make a bold move here and try to prove what the editorial says is too hard to prove…
I would like to prove both claims :
Claim 1 -
Even if you iterate infinitely from starting from 1 ; Then you will always obtain a ‘y’ for which y*y gives unique modulus with respect to all prime factors of Z ( Variable Z is already explained in the editorial )…
Claim 2 -
When you iterate linearly - The time complexity is = O(sqrt(n)) ( I think ) and you can pass all tasks without a TLE…
Proof for claim 1 :
You are trying to find a y for which y*y has unique modulus for all prime factors of Z.
( I will use equality signs here ; although all of them should be read as congruency symbols )
So basically you are trying to solve a system of linear congruence Which can be written as -
y * y = a1 ( mod p1 )
y * y = a2 ( mod p2 )
.
.
y * y = an ( mod pn )
Where p1 , p2 , p3 are prime factors of Z and (a1 != a2 != a3 … != an)
RIGHT…?
You are not bothered about what those a1 , a2… are…
Only concern is that all of them should be different ( No two of them should be same ) …
And p1 , p2 , p3 are prime factors of Z ( So Z = p1 * p2 * p3 … pn - DESCRIBED IN EDITORIAL )
And answer to the question is one of these primes…
So you want to find a y for which y * y satisfy all this…
Now from Chinese remainder theorem ; We can say that a solution to this system of equation always exist
This is because Chinese remainder Theorem says that two linear congruence equation :
x = b1 ( mod m1 ) and
x = b2 ( mod m2 ) have a solution if gcd(m1 , m2) divides b1 - b2…
In our system of equations ; you pick any two equations ; equations are in the format - something ( mod p ) where p is always prime…
Gcd of two distinct primes = 1( ALWAYS ) and 1 divides all numbers…
So take any two equations
y * y = a1 ( mod p1 )
y * y = a2 ( mod p2 )
gcd ( p1 , p2 ) = 1 and always divides a1 - a2 ( Irrespective of what a1 and a2 are )
So solution always exist ( Claim 1 Proved ) …
Proof for claim 2 : Why is anyone not getting a TLE ( Despite of infinite loops )
What guarentees that this y which we are trying to search is not far away from 1 and can be obtained by simple linear search brute…?
Answer : Chinese Remainder Theorem states that whatever our system of equations is ; The solution will be of the form :
y * y = V ( mod p1 * p2 * p3 … * pn )
And p1 * p2 * p3 … pn = Z ( Since these primes were created due to prime factorization of Z itself ) …
So solution is of format -
y * y = V ( mod Z ). ( We dont know this V )
Now see ; everyone is putting in first query a number ; whose square is greater than the biggest prime number less that 1e9.
Because of this ; if you observe - This Z is always something about 1e10
We dont know this V ; But since it is wrapped in ( mod Z ) and Z is approx = 1e10
So this V has to be less than 1e10. ( Because values in mod m world belongs to range [0,m-1] ).
So y * y = V ( We dont know this V ) But we know that this V is less than 1e10.
So y * y = something less than 1e10
So y = something less than 1e5 .
So when you iterate from 1 and indefinately ; then this y ( Which are searching always exist and is less than 1e5 )
So you always have a solution ; and you also will not get a TLE .
So you see that in the question ; you are avoiding TLE basically because query demanded y * y ( And not y itself ) .
So you won’t get a TLE if question demanded any power of y >= 2 when you are iterating linearly… ( And if power of y is greater than 2 ; then this process would be even faster ) .
However ; you cannot apply this linear brute if you had to respond in terms of y and not in y * y ( Because then that y could be anything from 1 to 1e10 and you can’t brute such a big range )…
Suggestions are always welcome… Tell me If I went wrong somewhere… However I tried to make this as detailed as possible ; Still if anything went unclear ; feel free to reach out ).
Just in case anyone needs to see how I coded it