How can we say that taking mod of square of ceil(sqrt(highest prime)) for all primes would be unique?
Because i thought that itās the highest prime we have and if we take x such that it covers the largest one, so our job would be done to cover all the primes.
I donāt know if thereās a mathematical proof but it worked out this way
Will this solution ( Suggested by harsh_7_pandey not have O(sqrt(n)) complexity per test case which I tried to show here : GUESSPRM-Editorial - #36 by ritesh1340 )
I may go wrong ; so I would be glad if some experienced person like you have a look at claim 2 of that comment to see if I went wrong somewhere or that approach has at max around 1e5 operationsā¦
Thanks in advanceā¦!
I think the reason behind this is the constraints of prime are upto 10^9. So by giving 10^5 Maybe we get a prime greater than 10^9. Because the square of 10^5 is 10^10. But if we give 35000(close to the sqrt of 10^9) or even 31623 (almost sqrt of 10^9) we get AC because the prime number is smaller than 10^9.
Almost AC solution (when x=10^5)
Solution(when x=31623 is used)got AC
So y * y = something less than 1e10
So y = something less than 1e5 .
I suppose this is not true. (y * y mod Z) < 1e10 , but this doestnāt mean that (y mod Z) < 1e5
And actually this is not CRT, because in CRT you need only variable in left side, not variable squared. For example, y * y = 2 mod 3 have no solutions at all
Can you please explain why you did this?
What if they have more than one intersection ??
How can you guarantee that such number exist b/w 2 to 10^4 ??
Afiaik such integer will be in range 1 to (multiplication of primes) ( it can be non perfect square as well).
I donāt have any concrete proof for this but only one of them will satisfy the equation.
On what basis are you claiming it ??
Because the solution will always exist, so one of them must satisfy both the equations.
The scenario would be different if there was no solution, but we donāt have to deal with that case.
I am asking why would they have āonly oneā number that satisfies it. why not ātwoā ?
I got it that there will be at least one satisfying it.
Actually I think there could be 2 when he cheats, So anyone of them could be accepted since it satisfies both the equation. I am not so sure about this though.
Editorialist code aint working when adding query equals to 100000
That logic is really incorrect as if more than one value matches, say 4-5 intersections, then that person is screwed only weak-testcase can help.
Can you explain CCC please? Even editorial is not really clearā¦
Actually I was not expecting my solution to get ACā¦
But I couldnāt find any exception in my code with my inputs.
Maybe you can try to break my logic if there are weak TCs.
That indeed can be the reason for the WA. Thanks for helping me outā¦
Noā¦noā¦I am not saying about you
ā¦ I did try that ideaā¦ And the prime factors were like these :-
2 3 5 7 17
2 3 5 7 101 (4-intersections)
Now, my code got confusedā¦and forgot
ā¦xdā¦which guy is the real guy. But unfortunately, I donāt remember that input anymore