Nu aveti permisiuni pentru a descarca fisierul grader_test17.in
Diferente pentru blog/meet-in-the-middle intre reviziile #51 si #50
Nu exista diferente intre titluri.
Diferente intre continut:
Notice that $i <= sqrt(n)$ and $j <= sqrt(n)$. Now our equality looks like this $p^(i ([sqrt(n)] + 1) + j)^ = q modulo n$. We can divide by $p^j^$ and get $p^(i[sqrt(n)] + 1)^ = qp^-j^ modulo n$.
Usingmeet in the middle becomes obvious. We can brute force through the numbers on each side of the equality and find a colision.
Now the application of meet in the middle becomes obvious. We can brute force through the numbers on each side of the equality and find a match.
The algorithm takes O(sqrt(n)) space and O(sqrt(n)) time. h2. Bidirectional search(interview question)
