結果

問題 No.1666 累乗数
コンテスト
ユーザー kozy
提出日時 2021-09-04 15:57:55
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 729 bytes
コンパイル時間 500 ms
コンパイル使用メモリ 82,540 KB
実行使用メモリ 255,844 KB
最終ジャッジ日時 2024-12-21 04:41:00
合計ジャッジ時間 42,311 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

def f(a):
  #L[a]は何番目か
  k=L[a]
  return a+1+int(k**0.5)
T=int(input())
n=10**18
L=set()
for i in range(1,(10**6+1)):
  if int(i**0.5)**2==i:
    continue
  for s in range(3,65,2):
    if pow(i,s)>n:
      break
    else:
      L.add(pow(i,s))
L=list(L)
L.sort()
for i in range(T):
  K=int(input())
  if K==1:
    print(1)
    continue
  if K==2:
    print(4)
    continue
  
  sita=0
  ue=1003331
  for j in range(100):
    this=(sita+ue)//2
    if f(this)>K:
      ue=this
    else:
      sita=this
    if ue-sita<=1:
      if f(ue)==K:
        print(L[ue])
        break
      if f(sita)==K:
        print(L[sita])
        break
      s=K-f(sita)
      a=L[sita]
      n=int(a**0.5)
      print((n+s)**2)
      break
0