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 constraints.
- 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 the number obtained in step 2.
- 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: