a^b < b^a

解説

実際に $a^b , b^a$ の値を計算して比較するのは、　$a^b , b^a \leq (10^{18})^{(10^{18})} = 10^{18 \times 10^{18}}$ より、あまりにも無謀です。よって、工夫を考えます。

とりあえず、与えられた不等式を変形してみます。$a,b$ の少なくともどちらか一方が $1$ のときや、$a = b$ のときの大小関係は明らか($a=1$ かつ $a \neq b$ のときのみ不等式成立)であるため、$a \neq b , 2 \leq a,b$ の場合を考えます。

$\displaystyle a^b < b^a \longleftrightarrow b\log a < a\log b \longleftrightarrow \frac{b}{\log b} < \frac{a}{\log a}$

ここで、 $\displaystyle f(x) = \frac{x}{\log x}$ とおくと $a^b < b^a \longleftrightarrow f(b) < f(a)$ が成り立てば良いと分かります。

また、 $f(x)$ のグラフを微分して描いてみると、$0 < x$ の部分においてグラフは下に凸の形をしており $x=e \fallingdotseq 2.71$ のとき極小値をとることが分かります。よって、$(e <) 3 \leq b < a$ のときは不等式が成り立ちます。

では、$a,b$ のどちらか一方が $2$ のときはどうなるのでしょうか。まず、$a=2$ のときを考えてみます。

$2^b < b^2 \longleftrightarrow 2^b-b^2 < 0$

ここで、$b>0$ において $2^b-b^2 = 0$ の解は $b=2,4$ であり、$2^b-b^2 < 0$ を満たす正整数 $b$ は $b=3$ のみであるため、$(a,b) = (2,3)$ のときのみ不等式が成り立ちます。

$b=2$ のときは、$a^2 < 2^a \longleftrightarrow 2^a-a^2 > 0$ より、$a=2$ のときと同様にして考えると $a$ が $2,3,4$ 以外の正整数であれば不等式が成り立ちます。

これまでの考察をまとめます。 不等式が成り立つのは、$(a,b)$ が以下の条件のうちいづれかを満たすときです。

• $a=1$ かつ $a < b$
• $3 \leq b < a$
• $(a,b) = (2,3)$
• $a \neq 2,3,4$ かつ $b=2$

これらの判定は当然 $O(1)$ でできるので、余裕で実行時間制限に間に合います。

追記

$\displaystyle f(x) = \frac{x}{\log x}$　の利用は $a^b,b^a$ の比較問題で威力を発揮しますが、今回の問題ではコーナーケースを考える必要がありなかなかしんどいと思います。