GUESSPRM-Editorial

How can we say that taking mod of square of ceil(sqrt(highest prime)) for all primes would be unique?

1 Like

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 :slightly_smiling_face:

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

1 Like

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

1 Like

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?

1 Like

What if they have more than one intersection ??

1 Like

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).

1 Like

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. :sweat_smile:

1 Like

Can you explain CCC please? Even editorial is not really clearā€¦ :stuck_out_tongue:

1 Like

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.

https://www.codechef.com/viewsolution/25295756

1 Like

That indeed can be the reason for the WA. Thanks for helping me outā€¦:pray::pray:

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