競プロ解法メモ

自分用のメモが主目的なので厳密性は求めないでください

yukicoder No.1022 Power Equation

yukicoder

問題：No.1022 Power Equation - yukicoder

解説を読んだものの、自分で消化するのに苦労したので記録。

まず、 $a^{b}=c^{d}$ を満たす条件を考えてみる。

$a=c=1$ のとき･･････ $b,d$ が何でもよいので $N^{2}$ 通り

$b=d$ のとき･･････ $a=c$ ならばよいので $N^{2}$ 通り

$a=c=1$ かつ $b=d$ のとき･･････ $N$ 通り

よって、全部で $\left(2N^{2}-N\right)$ 通り。これらは別に数えておいて、それ以外を考える。

$a,b,c,d\leq10^{9}$ なので、大き過ぎて実際に計算していくのは無理。そこで、自分で具体例を作ろうとしてみると次のような方法が見つかった。

$2^{12}=2^{12}$

$2^{2\times6}=2^{3\times4}$

$\left(2^{2}\right)^{6}=\left(2^{3}\right)^{4}$

$4^{6}=8^{4}$

これを逆に考えると、 $a^{b}=c^{d}$ という式は $a,c$ を変形して

$\left( t^{x}\right) ^{b}=\left( t^{y}\right) ^{d}$ （ただし $xb=yd$ ）

という形に出来ることが分かった（素因数分解の一意性から、必ずできることは証明できそう）。それでは、これにあてはまる $t,x,y,b,d$ を数え上げればいいかというと、大きな問題がある。それは、 $t,x,y,b,d$ が異なっていても $a^{b}=c^{d}$ の形にした時に同じ式になってしまう場合があることだ。例えば、

$4^{6}=16^{3}$

という式は

$\left(2^{2}\right)^{6}=\left(2^{4}\right)^{3}$

という形にも

$\left(4^{1}\right)^{6}=\left(4^{2}\right)^{3}$

という形にもできてしまう。よって、重複が出ないような数え上げ方が必要になる。そのために、数え上げのルールを１つ追加する。それは、

$x,y$ が互いに素になる場合だけに限定する

というもの。前述の例で言えば、下の形だけを許すことになり、上の形を重複して数えることはなくなる。さらに、但し書きの $xb=yd$ から $b=ky,d=kx$ （ $k$ は自然数）となるので、まとめると

$\left( t^{x}\right) ^{ky}=\left( t^{y}\right) ^{kx}$ （ただし $x,y$ は互いに素）

ということになる。あとは、 $x,y$ を全探索して、そのときの $\left(t,k\right)$ が何通りあるか数えていく。 $t^{x}=a\leq N$ なので、 $t$ が最小の2の場合を考えても、 $x$ は $\log _{2}N$ ぐらいまででよさそう。 $y$ についても同様。

提出コード：#645190 (Python3) No.1022 Power Equation - yukicoder