解法1

問題のように, 対数関数をimportし, \(\log_2 a\) と \(b\log_2 c\) の大小比較をすれば正解にな….らない. これはどういうことだろうか?

こんな話を聞いたことは無いだろうか ? (厳密性は犠牲にしている)

\(\dfrac{1}{3}=0.33333\dots\) である. 両辺に \(3\) を掛けると, \(1=0.99999\dots\)

\(0.99999\dots\) はどういう意味か? ということを正しく定義すれば上の式も説明がつくが, ここでは省略させていただく.

これと同様なことが計算機でも起こっている. 実際, 我々が日常生活に用いている \(10\) 進法の世界では, \(\left(\dfrac{1}{10} \right)_{(10)}=0.1_{(10)}\) である. しかし,

\[\left(\dfrac{1}{10} \right)_{(10)}=0.000110011\dots {}_{(2)}(=0. 0\dot{0} 01 \dot{1}_{(2)})\]

であり, \(0.1_{(10)}\) ですら, \(2\) 進法で有限個の桁で表すことができない. そこで, 計算機上ではある程度の桁で打ち切ったり四捨五入することによって実数を持つ.

しかし, そのときに誤差が発生してしまう. この誤差は一見小さいようにみえる. しかし, 行いたい計算によってはこの誤差が致命的になってしまう. 特に, 大小比較においてはこの問題がとても重要になる. 実際, この問題のテストケースにはこの問題が発生するような \(a,b,c\) が多数与えられている.

解法2

では, どのようにして比較する必要があるか? ここで, 対数に関する性質として, 以下がある. ただし, \(M,N>0, a>0, a \neq 1, k \in \mathbb{R}\) とする.

• \(k \log_a M=\log_a M^k\)
• \(a>1 \Rightarrow \left(\log_a M< \log_a N \iff M<N \right)\)

この性質を用いる. 判定すべき条件は

\[\log_2 a< b \log_2 c \iff \log_2 a < \log_2 c^b \iff a <c^b\]

となる.

\(a,b,c\) は整数より, \(a,c^b\) は整数となる.

先程, 実数は \(2\) 進数では有限桁で表せるとは限らないと述べた. これを整数に制限すると, 十分おおきなメモリを確保さえできれば, どんな整数でも正確にその値を記録できる. これは誤差が発生しないことを意味し, \(a<c^b\) かどうかという判定は厳密にできる.

従って, \(a<c^b\) かどうかを判定すれば良い. ここで, \(1 \leq b \leq 17, 1 \leq c \leq 13\) という制約から,

\[c^b \leq 13^{17}=8650415919381337933<9 \times 10^{18}\]

より, long long 型で足りうる.

以上から, \(a <c^b\) を判定すれば, 確実に正解できる.

補足

計算機上で実数を持ち, 以下のことを行う際には十分に注意しなければならない.

• 四捨五入
• 切り捨て
• 切り上げ
• 一致判定
• 大小比較