ともかく>>143はマトモに素因数分解してるのでネタということで。
んーと，a^b であるか否かを判定するのは P 問題なんですか？