Atcoder Beginner Contest284 D問題解説(Pythonコード付き)

はじめに　

　本記事はPythonでAtcoderにチャレンジしているけど、Pythonはコード例がないため解説がわかりにくい！と感じている方を対象としています。
　私自身大してレートも高くないので、不備等あるかもしれませんがご了承くださいm(_ _)m
　質問や指摘などもコメント等に書いてくださったら対応していきたいと考えていますのでどしどしコメントしてください。(内容がわかりにくいぞ！みたいな文句でもオールオッケーです笑)

Atcoder Beginner Contest284 D問題

　問題のURLはこちらです。Atcoder Beginner Contest284 D問題

使う手法

　今問題ではnを素因数分解する必要があります。
　今回は素因数分解のメジャーな手法である試し割り法を使ってnを素因数分解していきます。
　わざわざ名前を冠しているので複雑な手法なのかな？と思うかもしれませんが、単純に2,3,4,5・・・・と割っていって、余りがゼロになる値を調べていく方法です。
　ただし、素因数の捜索範囲に少し留意しなければなりません
　先ほど述べたように、単純に2,3,4,5・・・nと探していくと考えて実装すると、nの値が大きい場合にTLEしてしまいます。
　従って、一般的な試し割り法における素因数の捜索範囲は$\sqrt{n} $までとなっています。　
　AtcoderのD問題くらいので出てくるような値は大体この範囲で対応できる気がします。（今回は少し工夫しないといけませんが・・・・）

考え方　

　先程$\sqrt{n}$で対応できると言いましたが、今問題におけるNの範囲は$1\leqq N \leqq 9×10^{18}$となっているため、捜索範囲を$\sqrt{n}$として試し割り法を実装してもTLEになります。
　そこで、本問題のもう一つの制約である$N=p^2q$という制約を生かして、試し割り法に一つ素因数を見つけた段階で処理を終了するという処理を加えます。
　問題の制約からNは2種類の素因数しか持たないため、1種類でも素因数を見つけることができれば、もう1種類は簡単に計算できます。

実装例　

import math
from decimal import Decimal
#素因数分解する関数 
def p_func_re(n):
  """
  素因数を格納するリスト「arr」と、nをDecimal型に直した「temp」を作成する。
　(nをint型のまま扱うと、大きな値の際に有効数字の関係で誤差が生まれるため。)
  """
  arr = []
  temp = Decimal(n)
  #試し割り法を行う
  for i in range(2,int(math.sqrt(n))+1):
    if temp%i==0:
      #見つけた素因数がpなのかqなのか判定する。
      if temp%i**2 == 0 :
        l = Decimal(i)
        arr.append(l)
        arr.append(temp/l**2)
        break
      else :
        l = Decimal(i)
        arr.append(Decimal(math.sqrt(temp/l)))
        arr.append(l)
        break
  return arr
t = int(input())
 
for _ in range(t):
  n = int(input())
  arr = p_func_re(n)
  p = arr[0]
  q = arr[1]
  print(str(p) + " " + str(q))

計算量に関する記載

　公式解説では試し割り法の捜索範囲を$\sqrt[3]{N}$とすることで計算量の削減を図っていましたが、今回実装した方法でも実行することができました。(最大の実行時間は結構ギリギリでしたが笑)
　理由としては、pかqのどっちかが大きければ大きいほど、もう片方は桁数が小さくなるので早くループを抜けることができるからだと考えられます。
以下にNが最大桁数である18桁だった際の$p$ $p^2$　$q$の取りうる桁数を示します。
(ざっくりと考えたので間違ってたらすみません汗)

$p$	$p^2$	$q$
1桁	1~2桁	17~16桁
2桁	3~4桁	15~14桁
3桁	5~6桁	13~12桁
4桁	7~8桁	11~10桁
5桁	9~10桁	9~8桁
6桁	11~12桁	7~6桁

　この表通りに考えると、pまたはqの桁数が6桁程度の際に最大時間となりそうです。

最後に　

　今回の記事で、数式周りで変な改行が入っており、少し見にくくなっていてすみませんm(_ _)m
　数式埋め込みを初めて使ったこともあり、現在修正方法を探しています。　
　もしご存知の方がいらっしゃいましたら、コメントで教えていただけるとありがたいです。