ABC254_D – Together Square
問題
提出
3回目くらいで解けた
以下、解法をかく。
$ij$が平方数になる条件を考える。
ある数が平方数になるには、素因数分解したときに全ての素因数が偶数回現れる必要がある。
つまり、平方数をkとすると$k=p_{k_1}^{2x_1}p_{k_2}^{2x_2}…$となる。
$i*j$とした時、全ての平方数が偶数回現れるには、$iとj$の奇数回出現する素因数が一致している必要がある。
これを証明してみる。
簡単のため、$i$が次のように素因数分解できたとする。
$$i=p_{i_e}^{x_e}*p_{i_o}^{x_o}$$
ここで、$p_{i_e}$は偶数回現れた素因数、${x_e}$は現れた回数(偶数)、$p_{i_o}$は気数回現れた素因数、${x_o}$は現れた回数とする。
同様に$j$も以下のように素因数分解できたとする。
$$j=p_{j_e}^{x_e}*p_{j_o}^{x_o}$$
ここでも同様に、$p_{j_e}$は偶数回現れた素因数、${x_e}$は現れた回数(偶数)、$p_{j_o}$は気数回現れた素因数、${x_o}$は現れた回数とする。
この2つを掛けると、次のようになる。
$$i*j=p_{i_e}^{x_e}*p_{i_o}^{x_o}*p_{j_e}^{x_e}p_{j_o}^{x_o}$$
ここで、平方数になるには素因数が偶数回現れている必要があるので、$ij$が平方数になるには、$p_{i_o}^{x_o}*p_{j_o}^{x_o}$が偶数回現れている必要がある。
$p_{i_o}^{x_o}*p_{j_o}^{x_o}$が偶数回現れるためには、$p_{i_o}=p_{j_o}$である必要がある。
よって、$i*j$とした時、全ての平方数が偶数回現れるには、$i,j$の奇数回出現する素因数が一致している必要がある。
N以下の数字を素因数分解するには、エラトステネスの篩を使う。
前計算で、$O(N\log\log N)$、素因数分解に$O(\sqrt N)$かかる。
$1..N$の数字を素因数分解して、奇数回出現する素因数を求めるので、$O(N \sqrt N)$になる。
実装上、奇数回出現する素因数をそのまま保存することは難しいので、奇数回出現した素因数をかけたものを保存することにする。
奇数回出現した素因数を掛けると一意に定まり、素因数を掛けたものを素因数分解すると一意に定まるので、「奇数回出現する素因数をそのまま保存する <=> 奇数回出現した素因数をかけたものを保存する」となる。
この方法は公式解説の$i/f(i)$と一致する。
コメント