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
3 Likes
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
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
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.
https://www.codechef.com/viewsolution/25179439
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.
https://www.codechef.com/viewsolution/25182120
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