I get this. But I don’t understand what you are trying to say here.
Okay… glad to see that you are replying…
Now let say someone tells you that I am having a prime number in my head which is less that 20…
Then for that case ; I think q1 = 11 and q2 = 13 is a good enough query right…?
Bcos if upper limit was 20 ; then you should be choosing some number between sqrt(20) and 20.
So both 11 and 13 satisfy… But when I give you response = 1 and 1 for both queries ; you cant determine whether the prime number I have in my head = 2 or = 3.
Thats why I said this:
Even I had proceeded by the same approach as you told ( in the contest ) ; after after working around it ; I noticed that It fails… SO IT MIGHT ( AND SHOULD ALSO FAIL ON OTHER BIG TEST CASES ) … Thats why I never proceeded with it… ( Did’nt knew that test cases were weak and this kind of approach would also fetch me and AC )
Mine is also the same approach
Okay… So I am gonna make a bold move here and try to prove what the editorial says is too hard to prove…
I would like to prove both claims :
Claim 1 -
Even if you iterate infinitely from starting from 1 ; Then you will always obtain a ‘y’ for which y*y gives unique modulus with respect to all prime factors of Z ( Variable Z is already explained in the editorial )…
Claim 2 -
When you iterate linearly - The time complexity is = O(sqrt(n)) ( I think ) and you can pass all tasks without a TLE…
Proof for claim 1 :
You are trying to find a y for which y*y has unique modulus for all prime factors of Z.
( I will use equality signs here ; although all of them should be read as congruency symbols )
So basically you are trying to solve a system of linear congruence Which can be written as -
y * y = a1 ( mod p1 )
y * y = a2 ( mod p2 )
.
.
y * y = an ( mod pn )
Where p1 , p2 , p3 are prime factors of Z and (a1 != a2 != a3 … != an)
RIGHT…?
You are not bothered about what those a1 , a2… are…
Only concern is that all of them should be different ( No two of them should be same ) …
And p1 , p2 , p3 are prime factors of Z ( So Z = p1 * p2 * p3 … pn - DESCRIBED IN EDITORIAL )
And answer to the question is one of these primes…
So you want to find a y for which y * y satisfy all this…
Now from Chinese remainder theorem ; We can say that a solution to this system of equation always exist
This is because Chinese remainder Theorem says that two linear congruence equation :
x = b1 ( mod m1 ) and
x = b2 ( mod m2 ) have a solution if gcd(m1 , m2) divides b1 - b2…
In our system of equations ; you pick any two equations ; equations are in the format - something ( mod p ) where p is always prime…
Gcd of two distinct primes = 1( ALWAYS ) and 1 divides all numbers…
So take any two equations
y * y = a1 ( mod p1 )
y * y = a2 ( mod p2 )
gcd ( p1 , p2 ) = 1 and always divides a1 - a2 ( Irrespective of what a1 and a2 are )
So solution always exist ( Claim 1 Proved ) …
Proof for claim 2 : Why is anyone not getting a TLE ( Despite of infinite loops )
What guarentees that this y which we are trying to search is not far away from 1 and can be obtained by simple linear search brute…?
Answer : Chinese Remainder Theorem states that whatever our system of equations is ; The solution will be of the form :
y * y = V ( mod p1 * p2 * p3 … * pn )
And p1 * p2 * p3 … pn = Z ( Since these primes were created due to prime factorization of Z itself ) …
So solution is of format -
y * y = V ( mod Z ). ( We dont know this V )
Now see ; everyone is putting in first query a number ; whose square is greater than the biggest prime number less that 1e9.
Because of this ; if you observe - This Z is always something about 1e10
We dont know this V ; But since it is wrapped in ( mod Z ) and Z is approx = 1e10
So this V has to be less than 1e10. ( Because values in mod m world belongs to range [0,m-1] ).
So y * y = V ( We dont know this V ) But we know that this V is less than 1e10.
So y * y = something less than 1e10
So y = something less than 1e5 .
So when you iterate from 1 and indefinately ; then this y ( Which are searching always exist and is less than 1e5 )
So you always have a solution ; and you also will not get a TLE .
So you see that in the question ; you are avoiding TLE basically because query demanded y * y ( And not y itself ) .
So you won’t get a TLE if question demanded any power of y >= 2 when you are iterating linearly… ( And if power of y is greater than 2 ; then this process would be even faster ) .
However ; you cannot apply this linear brute if you had to respond in terms of y and not in y * y ( Because then that y could be anything from 1 to 1e10 and you can’t brute such a big range )…
Suggestions are always welcome… Tell me If I went wrong somewhere… However I tried to make this as detailed as possible ; Still if anything went unclear ; feel free to reach out ).
Wrote one below…! ( Not sure if you were looking for the same what I tried to prove )
It’s simple take a number whose square is larger than the largest prime ( I’ve chosen 31700, no obvious reason, first I chose 100000)
Give it to the shef and we’ll get a mod-ed value
Then calculate ques x ques - modVal
Then find all prime factors to it.
Remove those factors whose value is lower than the modVal, because if they are a factor then we would have a much lower modVal.
if the remaining array has one element, its the answer
Else give one of its largest prime factors as a query
Then we will get another modVal2, calculate largeP x largeP - modVal2
find prime factors of this one
Check if there is any common factors between these two.
It will be our factor
It is quite obvious that you can’t ask two large prime numbers. Because if you do, you can’t distinguish 2 or 3 (for both you will be answered 1 1). Actually, I don’t know criterion of choosing this two numbers and will be glad if someone tell this
My solution is based on another facts, which are hard to prove on paper, but I simply brute-force all non-proven cases.
I am absolutely sure that at least non-adaptive testcase are very strong. If I am not mistaken, there are ~10,000 different primes in all testcases, which includes all small primes (first 1000) and many big or medium primes. Even if there is case on which some solution fails, how can one avoid this?
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).
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.
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.