BOJ 26008 - 해시 해킹

June 19, 2023

처음에 $P_0$ 으로 가능한 값은 $M$ 개가 있다.

$N=2$ 라고 해보자. $M$ 개의 $P_0$ 값에 모두 $A^0=1$ 이 곱해졌으므로 여전히 $0 \sim M-1$ 값들이 있다.

$A_0$ 에 집중하지 말고 $\sum_{i=1}^{N-1}P_iA^i$ 에 집중하자.

이건 결국 $M$ 으로 나누었을 때 나머지가 $0 \sim M-1$ 일 것이고 어떤 것이 오든 $P_0$ 에 의해 $H$ 가 될 수 있다.

따라서 $M^{N-1}$ 이 정답이다.

You may also enjoy