Here’s an explanation of my solution :
Suppose that we have queried A and B and received r_1 and r_2 respectively as the remainder. Then P should be a divisor A^2-r_1 and B^2-r_2, greater than both of the remainders. So we need to choose such A and B that P will be unique regardless of r_1 and r_2. Note that if r_1 = 0, then we can check every prime divisor of A (except for one). So we pick such A that is a multiple of at most two primes. As for B, a prime will do just fine. Combining these simple observations and the fact that P = 2 is the most annoying case, I found 43222 (since it omits the P = 2 case) and 40009 (there’s a lot of them, you can find them by trial, mine took only two attempts).
1 Like
If you say that test data is weak, propose test on which at least one accepted solution fails. And argue how can I predict such solution and made countertest.
i thought uptill the subclaim and then it struck me that the probability of randomly chosen x to give same x^2 % p for p = p1, p2 must be very low. So i chose x randomly and checked on all the prime factors. Though i kept maximum number of tries to be 10^5 , using 10 tries, 5/10 cases passed. I did not compute the probability though
There were weak testcases in this problem.
Because I made the modular equations and after about 30 WA and TLE -1.0000 , I got AC.
I was just putting random numbers and finding largest prime factor of GCD when I stumbled across 102 ans 111 which gave ACs in certain tasks and TLEs in others.
https://www.codechef.com/viewsolution/25109861
These tasks which got ACed by 102 and 111 did not get AC by other numbers.
https://www.codechef.com/viewsolution/25109375
So, I just multiplied any number with 102 and 111 and then raslised that due to testcases, they gave ACs.
https://www.codechef.com/viewsolution/25154324
I think the problem was when Shef took primes to be 2 and 3 which were now solved as 102 is divisible by 2 and 103 is divisible by 3.
1 Like
u may check all common factor must be greater than a and b means ans given by system.
It is obvious that your first submission is TLE, as you do while (n % 2 == 0) where n can be equal to 0 (if prime is quite big).
In second submission (as I mentioned already) your solution can’t distinguish 2 and 3.
So, in which testcase last solution should fail?
Last solution is AC but I think it would fail in testcases designed to fail it specifically
Please, show me how to design one?
Even so, how can I predict this solution?
Or should I make as many testcases as there are primes under billion?
I don’t understand what do you mean by predict
You just said that testcases were weak.
What is strong testcases for you?
Under “predict” I mean make a countertest.
1 Like
I’ll try to make one. But I think it’s too random for me to choose two numbers which don’t have countersolution so I think they’ll exist.
@bohdan
What are you implying?
That’s the point - it is too random to make countertest against any solution. And, as for me, it has nothing common with testcases weakness.
Well, no need of the Chinese theorem or any other predefined mathematical approach.
the question works well even with an easier brute force approach.
Here is the approach I used for AC in all the test cases:
- Throw the maximum number possible in the constraint (100000) (because the square of 10,000 goes to 10000000000) which is maximum possible according to the constraint.
- suppose the input of the result is b;
so (100000*100000 -b) is a factor of the prime P. - compute all the prime factors of such a number.
- input all the prime factors into a set and calculate the total number of prime factors of the number.
- for i in range of 2 to 10000, find the square for which mod of every element in the set of factors gives a unique number. (the size of the set of all resulting mods will be equal to the set of prime factors of 1000000000000-b).
- output the square found in step 5.
- calculate the number for which the input satisfies the given condition.
Here you have your answer with just a simple brute force approach.
The link to the solution:
https://www.codechef.com/viewsolution/25220569
2 Likes
Yes, such solutions got AC. But we can’t prove this solution complexity, that’s why solution in editorial is much more complicated, but with proven complexity and correctness.
2 Likes
Here’s an interesting observation.
Refer to the code 1 and it’s verdict ans well as code 2 and it’s verdict.
Amost AC solution code 1
AC solution code 2
The only change in both the case is the value of x from 10^5 to 35000.
I don’t know if there’s a reason behind it or i just got lucky.
2 Likes
Just reminding a typo in point 1 it should be P>x^2
It’s funny but obvious at the same time, that we won’t be going any far by doing such “Jugaad”. 
So better focus on learning new algos to tackle any problem.
1 Like
Yeah that is the main aim. Learning and becoming better.
Yup, thanks for figuring it out.
Same thing happened with me also. Still not able to figure out, what was the error.