Editorial
Some of you might have wondered why classical computation is required in a quantum programming contest.
In Shor's algorithm, if classical computation is performed without considering its time complexity, the effort put into the quantum computation becomes meaningless. Therefore, having some knowledge of classical computation is necessary.
If you follow the problem statement directly and compute naively, you will encounter Time Limit Exceeded (TLE) or Memory Limit Exceeded (MLE) errors. However, by repeatedly squaring, you can reduce the number of multiplications.
Additionally, during the calculation, taking the modulus whenever the value exceeds prevents the number of digits from growing indefinitely.
Sample Code
Below is a sample program:
def solve(n: int, a: int, L: int) -> list:
result = [a]
for _ in range(n - 1):
result.append(result[-1] ** 2 % L)
return result