I am unable to figure out a simple method to find m for which (m*m) \mod n is maximum. I think there should be a O(\sqrt{n}) or better solution.
My thought is that maximum occurs for one of m in set \{sqrt{n}, \sqrt{2n} ... n} if n is not a perfect square. If it is, then the set element predecessors are considered. But this is also O(n)
Any hint will be helpful
Can you clarify the constraints of m?
Its written in the title, earlier there was a typo! Corrected it. N <= 1e9
That’s not what I am asking.
I want to know what is the maximum value of M that we can print.
Actually I don’t know, does it make a difference if m < n or m > n ? I dont know thats why I am asking. Is is possible in some case that max is attained only for some m > n.
Suppose for a significantly large value m^2 = kn - 1 where k is any integer then you can attain maximum value and you don’t really know where.
If this is the case then you can try to find a ‘k’ such that kn - 1 is a perfect square.
But I can’t be sure.
Can you provide a link to the problem.
I understand your point, actually question is from my internship test (samsung research - parichay)
No idea about that.
Was it online or offline?
Or do you have any link to the problem?
Online, No they dont provide link, it was some software which doesnt allow clicking out of the window.
Ok
Let’s try to find largest x such that there exists a which satisfies a^2 \equiv x \mod n
(Also known as a quadratic residue mod n).
To do that, we first factor n, into prime factors. Iterate i from n-1 to 0. (Trust me it’s not O(n) but O(\sqrt{n}log^2 n)). Check if i is a quadratic residue by an extension of Euclid’s criterion When you find i that is a quadratic residue mod n, Then use Tonelli Shanks algorithm To find m.
You have to use this for all p^k dividing n and merge them using the chinese remainder theorem.
It will go at through at most O(\sqrt{n}) numbers, because the \lfloor \sqrt{n} \rfloor^2 will not exceed n, and the difference between \lceil \sqrt{n} \rceil^2 and \lfloor \sqrt{n} \rfloor^2 will not be more than O(\sqrt{n})
Was my statement correct about the m*m = k * n - 1 thing??
Are these kind of questions really asked in interviews ( I personally have 0 experience) but I have read many interview questions but never found a question which required that much math but mostly they were data structure based.
Can you shed some light??
@everule1
I don’t think that is correct.
As for interviews, I don’t really know anything about interviews. I’ve never really bothered checking interview questions and I’m too young to get an interview.
Thanks a lot, though its a bit difficult for me, I will read the methods listed to understand better. Thanks!!