P-NP 문제

$P=N\times P$를 정리하면 $(N-1)P=0$이다. 따라서 $N=1$ 또는 $P=0$인 경우에만 등식이 성립한다.

정답 코드는 두 조건 중 하나 이상이 참인지 검사한다. 나이브 코드는 $N\times P$를 직접 계산하여 $P$와 비교한다. 두 방법 모두 케이스당 시간과 추가 공간 복잡도가 $O(1)$이며, 전체 시간 복잡도는 $O(T)$이다. 이 문제는 작은 정수 연산만 필요하므로 두 방법 모두 전체 제약에서 사용할 수 있다.

$|NP|\leq 10^6$이고 $|(N-1)P|\leq 1\,001\,000$이므로 32비트 부호 있는 정수로도 안전하게 계산할 수 있다. 도 가능하므로 양변을 무조건 로 나누어서는 안 된다.

Solution written by GPT