Solve the Exponent — Solution & Editorial

Back to the Problem

Baby-step giant-step: write x = in − j with n = ⌈√M⌉. Tabulate A^j for the baby steps, then multiply B by A⁻ⁿ repeatedly for the giant steps, matching against the table.

Complexity: O(√M)

Watch out: Store the FIRST (smallest) j per residue so ties yield the minimum x, and verify matches to reject false positives from the table.