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