A link to my solution, https://www.codechef.com/submit/complete/25322812
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
1 Like
How do you come up with this idea of start from sqrt(max prime factor)??
1 Like
But why you start from sqrt(max prime factor)?
Is there any specific reason?
1 Like
Thanks i got it finally😅
1 Like
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.
3 Likes
nice one:smiling_face_with_three_hearts:
I solved with the chinese remainder theorem as well.
The first query I used was fixed, 31623.
The second query would be a number constructed using chinese remainder theorem so that the remainder straight up identified the prime uniquely.
1 Like
Need help with my approach, not sure where I went wrong. Works locally, but gives WA on CC.
https://www.codechef.com/viewsolution/25310646
A bit offtopic but would love to know what does this line do?
#pragma GCC optimize("O3", "unroll-loops", "omit-frame-pointer", "inline")
Till now, is it proved that an unique value exists that we WILL achieve quickly that will satisfy the condition that square of the number has unique remainder wrt some primes p1, p2, p3… pn ? I dont see any mathematical proof…
I cant understand why this works . How do you proof that there is only one number who is divisor of the number from the 2nd query
1 Like
Why us the prime factorization not getting TLE?Suppose I choose 99999 as my initial query and p=2 so the remainder would be 1 so i am left with 9999800001-1=9999800000 so for finding prime factors it will take about 10^5 time and the test cases will take 10^3 so in total 10^8.
10^8 can run fine within 2\text{ s} since you aren’t doing anything “heavy”.
2 Likes
welcome to our community
A way to specify compilation flags within the source code. Forces O3 level optimization in some places.
That’s the beauty of competitive coding
2 Likes