But It does not work out always… I was not able to figure this out ; But one of my friends ( @whozthis ) did…
He told me let say you have prime factorization of some number giving unique primes as = { 2,3,5,7,11,13 } .
Then you would ask ceil(sqrt(13) ) as query = 4.
For 4 ; you will get same value of modulus from 3 and 5.
Since 16 = 1 ( mod 3 )
And 16 = 1 ( mod 5 ).
I tried to prove that such a number exists in a short range
here : GUESSPRM-Editorial - #36 by ritesh1340 ( In claim 2 )
and here : GUESSPRM-Editorial - #91 by ritesh1340
… Could you please see to it if the proof has some flaw… Would highly appreciate your help…! Thanks in advance…!
So, is it that tc’s are weak?
how you came up with 32000 and 33002, why not something else how u get these numbers.
so that num = 2 mul3 mul5 mul 7 mul 11 mul 13= 30030
as num= x^2-ans1
ans1= (31623*31623) - (30030)
i.e. ans1=999984099
Now if you check
(3162331623)%3=0
But (3162331623)%5=4
And as i said i would take only that prime numbers which would give x^2%p=ans1 which both of them are not giving.
So there are some flaws in what you are trying to say i think.
I have done this problem with a different approach . I firstly give 178 as query then i checked if ans_to_query==178^2 then it is sure that prime number is greater than 178^2 and it can be easily observed that factors of 10^9 only contain one no. greater than 1782 ( which is sqrt(sqrt(10^9)) ) no if ans_to_query==178^2 then my second query is 31623 and by which i can get one prime number greater than 31k but less than 10^9
similarly if ans_to_query<1782 then my second query is 14 because by similar logic a no greater than 196 has only one prime factor greater than 14 and for smaller prime i check common prime factors in both query results .
I know It is not easy to understand but for better understanding here is my code:https://www.codechef.com/viewsolution/25292195
No my friend ; What I meant was that you can’t generalize the fact that you can take a perfect square after the biggest prime of the list of primes and this perfect square will give unique modulus with respect to all the primes…
And why this can’t be generalized is because you have a counter example for this ( Which @whozthis told me and I gave it to you… )
Now ; there can be a lot more examples which might fail you with that kind of approach ( Irrespective of the fact whether those examples were present in test cases or not ).
Also ; That example only tries to tell you that you might obtain a perfect square which is not giving unique modulus with respect to all primes.
This fact has nothing to do with whether you are going to end up with that sort of a number when you give 31623 as first query… ( I am least bothered about it ).
BUT POINT IS THAT IF YOU HAVE A LIST OF PRIMES - THEN A PERFECT SQUARE JUST BIGGER THAN THE BIGGEST PRIME OF THE LIST WONT ALWAYS GIVE UNIQUE MODULUS WITH RESPECT TO ALL PRIMES.
And the reason for this was very simple - you need just one example to dis-prove your claim ( Or prove my claim ) ( Which @whozthis already suggested ).
That’s it ( No matter that 31623 as query 1 will or will not lead you to those primes ).
Sure, you are correct
hilarious:rofl:
Brilliant mathematical solution.I would suggest everyone to read the editorialist’s solution and not skip reading just because you have solved using brute force
One more CRT link-Chinese Remainder Theorem | Brilliant Math & Science Wiki
although editorial looks tough when you skim through it but when you understand number theory it is not tough although sometimes it takes a little time to understand
I have written the solution as said in this editorial, but still I am receiving wrong answer verdict. Moreover, I had placed assertions for -1 and No, but none of these assertions reported anything. Why didn’t the judge return -1 or No ? and how do I debug my code.
Thanks in advance
Glad to help… 
I don’t understand why you said to choose sqrt(max prime factor), i have tried an example like
I choose prime to mod= 13
num= 214*214 - 214%13= 45786
Prime factor= 2,3,13,587.
Ceil(sqrt(587))= 25, then how this can satisfy the previous results,
Will u explain it …
Thanks
Why you chose 214?
i don’t get it.
Let’s say you choose p = 13
So acc to my soln.
For first query:
x^2%P= ans1
Here = x=31623,P=13,ans1 will be 10
So we need to compute prime factors of x^2-ans1= (31623*31623)-10=1000014119.
Prime factorization of 1000014119 = 13,271,373,761;
SO we will put second query of x as ceil(sqrt(761))=28;
Now x^2=784
784%13=4 , 784% 271 = 242 , 784 % 373 = 38 , 784 % 761 = 23
Which are unique so, we can get our ans as 13
How do you come up with this idea of start from sqrt(max prime factor)??
But why you start from sqrt(max prime factor)?
Is there any specific reason?
Thanks i got it finally😅
my approach - gave n=100000 to chef. Found all the the prime factors of n^2 - a. Chose only those primes that are grater than a. Say p1, p2 … . All the prime factors now qualify to be the chef’s prime. Even if he cheats, his new prime will be from p1,p2… . Now I iterate from 1 to 100000 and find, that i^2 which gives different remainders when divided by p1, p2 … . I give this new number i to the chef. Then I match which prime number’s remainder matches with chef’s output. That prime is my answer.