Sure! Thanks…
not capable to explain actual logic ATM. I hacked that question’s test cases
It’s tough to break such approaches in question and I feel setter tried his best
@hetp go through the editorial GUESSPRM- A simple brute force approach. Everything will be clear.
Your solution is far more intuitive. Thanks.
No I meant to say that let say if x = 4 ( mod 7 )
Then x can take any values of the form 4 + 7*d.
That means x can be any term of that arithmetic progression ( 4 + 7*d )
But one of the values of x is necessarily = 4 right…?
So if y * y = something less than 1e10 ( Since y*y = something ( Mod Z ) and Z < 1e10 ; Then y * y will take a lot of values upto infinity ;
But one of the values of y * y is necessarily less than 1e10 correct…?
And if one value of y * y exists less than 1e10 ; then for that value y < 1e5.
So We will always find at least one value less than 1e5 ( Enough to do a linear search and avoid TLE… )
Yes I do agree that there will be a lot of values of ‘y’ for which this will not be true… But my claim stresses on the fact that we need to find only one value of y…
And that one value is ALWAYS LESS THAN 1e5…
Is this correct…? ( Experienced coders @l_returns @anon55659401 @bohdan )
Eagerly waiting for the reply… Thanks in advance…!
And all this is based on my earlier comment : GUESSPRM-Editorial - #36 by ritesh1340
But It does not work out always… I was not able to figure this out ; But one of my friends ( @whozthis ) did…
He told me let say you have prime factorization of some number giving unique primes as = { 2,3,5,7,11,13 } .
Then you would ask ceil(sqrt(13) ) as query = 4.
For 4 ; you will get same value of modulus from 3 and 5.
Since 16 = 1 ( mod 3 )
And 16 = 1 ( mod 5 ).
I tried to prove that such a number exists in a short range
here : GUESSPRM-Editorial - #36 by ritesh1340 ( In claim 2 )
and here : GUESSPRM-Editorial - #91 by ritesh1340
… Could you please see to it if the proof has some flaw… Would highly appreciate your help…! Thanks in advance…!
So, is it that tc’s are weak?
how you came up with 32000 and 33002, why not something else how u get these numbers.
so that num = 2 mul3 mul5 mul 7 mul 11 mul 13= 30030
as num= x^2-ans1
ans1= (31623*31623) - (30030)
i.e. ans1=999984099
Now if you check
(3162331623)%3=0
But (3162331623)%5=4
And as i said i would take only that prime numbers which would give x^2%p=ans1 which both of them are not giving.
So there are some flaws in what you are trying to say i think.
I have done this problem with a different approach . I firstly give 178 as query then i checked if ans_to_query==178^2 then it is sure that prime number is greater than 178^2 and it can be easily observed that factors of 10^9 only contain one no. greater than 1782 ( which is sqrt(sqrt(10^9)) ) no if ans_to_query==178^2 then my second query is 31623 and by which i can get one prime number greater than 31k but less than 10^9
similarly if ans_to_query<1782 then my second query is 14 because by similar logic a no greater than 196 has only one prime factor greater than 14 and for smaller prime i check common prime factors in both query results .
I know It is not easy to understand but for better understanding here is my code:https://www.codechef.com/viewsolution/25292195
No my friend ; What I meant was that you can’t generalize the fact that you can take a perfect square after the biggest prime of the list of primes and this perfect square will give unique modulus with respect to all the primes…
And why this can’t be generalized is because you have a counter example for this ( Which @whozthis told me and I gave it to you… )
Now ; there can be a lot more examples which might fail you with that kind of approach ( Irrespective of the fact whether those examples were present in test cases or not ).
Also ; That example only tries to tell you that you might obtain a perfect square which is not giving unique modulus with respect to all primes.
This fact has nothing to do with whether you are going to end up with that sort of a number when you give 31623 as first query… ( I am least bothered about it ).
BUT POINT IS THAT IF YOU HAVE A LIST OF PRIMES - THEN A PERFECT SQUARE JUST BIGGER THAN THE BIGGEST PRIME OF THE LIST WONT ALWAYS GIVE UNIQUE MODULUS WITH RESPECT TO ALL PRIMES.
And the reason for this was very simple - you need just one example to dis-prove your claim ( Or prove my claim ) ( Which @whozthis already suggested ).
That’s it ( No matter that 31623 as query 1 will or will not lead you to those primes ).
Sure, you are correct
hilarious:rofl:
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
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
Glad to help…
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