No It does not always work… I also thought of this ; but I rejected it…
Reason : What you say is just a conjecture and I need only one example to disprove that claim right…
Forget about those very big numbers uptil 1e9… Lets think in a small range…
Suppose you input queries q1 = 11 and q2 = 13.
For these ; I give you responses r1 = 1 and r2 = 1 respectively…
So now go ahead and tell me whether the prime which I have in my head is 2 or 3…?
One of the simplest solutions, always asks 100000 and 10002. then every prime under 1e9 will have different remainder so you can easily find the prime looping throw divisors of the queries. To find those two numbers, I randomly picked 100000 and iterate to find the second number so that every prime will yield a different answer.
We have similar usernames too.
Are you saying that the TCs are weak?
Maybe… but maybe I am wrong and I have not understood what you were saying…
Tell me… can you tell whether prime = 2 or 3… I cannot…
And even If you cannot… then most probably yes TC were weak…
you are on the next level !
I have not selected 11 and 13. The number must be between sqrt(n) and n (n=10^9), and there is also another relation between these 2 numbers, which I am not so sure about right now.
I think you are talking about this case mentioned in the problem:
“Shef will sometimes cheat: he can change his prime any number of times during the game (even after you tell him your guess), but only in such a way that all his answers to your previous questions remain correct.” If so, the answer can be anyone of the 2.
Surprisingly my approach was a little different.
Here is what i did.
I am still unsure how it worked 
No No my friend… see you have chosen numbers between sqrt(n) and n so that the largest prime less than 1e9 = 999999937 can give some modulo not equal to the square of your chosen number right…?
I mean you dont choose small number like 11 and 13 bcos if the prime that chef had chosen was = a prime greater than 200 ( Just assumption ) ; then for both 11 and 13 ; you would get response = 121 and 169 respectively…
And 11 * 11 - 121 = 0
And 13 * 13 - 169 = 0 So these 0s were for no use for you …
Are we on the same page till here…? ( If you say yes then I think we will have an interesting discussion )
actually the editorial is also dong the same but it looks scary:upside_down_face:
I get this. But I don’t understand what you are trying to say here.
Okay… glad to see that you are replying…
Now let say someone tells you that I am having a prime number in my head which is less that 20…
Then for that case ; I think q1 = 11 and q2 = 13 is a good enough query right…?
Bcos if upper limit was 20 ; then you should be choosing some number between sqrt(20) and 20.
So both 11 and 13 satisfy… But when I give you response = 1 and 1 for both queries ; you cant determine whether the prime number I have in my head = 2 or = 3.
Thats why I said this:
Even I had proceeded by the same approach as you told ( in the contest ) ; after after working around it ; I noticed that It fails… SO IT MIGHT ( AND SHOULD ALSO FAIL ON OTHER BIG TEST CASES ) … Thats why I never proceeded with it… ( Did’nt knew that test cases were weak and this kind of approach would also fetch me and AC )
Mine is also the same approach
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 ).
Wrote one below…! ( Not sure if you were looking for the same what I tried to prove )
It’s simple take a number whose square is larger than the largest prime ( I’ve chosen 31700, no obvious reason, first I chose 100000)
Give it to the shef and we’ll get a mod-ed value
Then calculate ques x ques - modVal
Then find all prime factors to it.
Remove those factors whose value is lower than the modVal, because if they are a factor then we would have a much lower modVal.
if the remaining array has one element, its the answer
Else give one of its largest prime factors as a query
Then we will get another modVal2, calculate largeP x largeP - modVal2
find prime factors of this one
Check if there is any common factors between these two.
It will be our factor
It is quite obvious that you can’t ask two large prime numbers. Because if you do, you can’t distinguish 2 or 3 (for both you will be answered 1 1). Actually, I don’t know criterion of choosing this two numbers and will be glad if someone tell this 
My solution is based on another facts, which are hard to prove on paper, but I simply brute-force all non-proven cases.
I am absolutely sure that at least non-adaptive testcase are very strong. If I am not mistaken, there are ~10,000 different primes in all testcases, which includes all small primes (first 1000) and many big or medium primes. Even if there is case on which some solution fails, how can one avoid this?