1060 - れどこだ目指すよ！　(；`・ω・）

1060 No Story

LCM(a,b)=Lとなるa,bの組み合わせの数．前はa,bをループでまわしてバッチリTLEもらったはず．

wikipediaのページにあるように，
$a=\Pi p^{e_p(a)}$ と $b=\Pi p^{e_p(b)}$ のとき $lcm(a,b)=\Pi p^{max(e_p(a),e_p(b))}$ となるので，lcm(a,b)=LのときLを素因数分解すればそれぞれの $max(e_p(a),e_p(b))$ の値がもとまる．
$p_L=max(e_p(a),e_p(b))$ とすると， $e_p()$ が0以上 $p_L$ 以下なので， $e_p(a)$ と $e_p(b)$ の組み合わせは $2p_L+1$ ．この組み合わせをそれぞれのpについて計算して掛けてやればa,bの組み合わせの数になる．
問題は $a \leq b$ なので， $a=b$ の時は一組なのを考えて，(結果+1)/2が答え．L=1の時は(1,1)だけなので，答えは1なのを忘れず．