結果
問題 | No.1666 累乗数 |
ユーザー |
👑 ![]() |
提出日時 | 2021-09-03 21:50:39 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,862 bytes |
コンパイル時間 | 386 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 622,928 KB |
最終ジャッジ日時 | 2024-12-15 12:30:54 |
合計ジャッジ時間 | 46,580 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 3 TLE * 2 MLE * 14 |
ソースコード
#floor(a^(1/k)) を求める.def Floor_Root(a,k):"""floor(a^(1/k)) を求める.a:非負整数k:正の整数"""assert 0<=a and 0<kif a==0: return 0if k==1: return a#大体の値を求める.x=int(pow(a,1/k))#増やすwhile pow(x+1,k)<=a:x+=1#減らすwhile pow(x,k)>a:x-=1return x#ceil(a^(1/k)) を求める.def Ceil_Root(a,k):"""ceil(a^(1/k)) を求める.a:非負整数k:正の整数"""assert 0<=a and 0<kif a==0:return 0if k==1:return a#大体の値を求める.x=int(pow(a,1/k))+1#増やすwhile pow(x,k)<a:x+=1#減らすwhile a<=pow(x-1,k):x-=1return xdef kth_Power(a,k):""" 整数 a が k 乗数かどうかを求め, そうならば, b^k=a を満たす k を返す.[Input]a:intk:int (k>0)[Output]存在しない : None存在する : b^k=a を満たす b"""a_abs=abs(a)if a: sgn=a//a_abselse: sgn=0b=Floor_Root(a_abs,k)if pow(sgn*b,k)==a:return sgn*belse:return Nonedef Binary_Search_Small_Count(A,x,equal=False,sort=False):"""2分探索によって,x未満の要素の個数を調べる.A:リストx:調べる要素sort:ソートをする必要があるかどうか(Trueで必要)equal:Trueのときはx"未満"がx"以下"になる"""if sort: A.sort()if len(A)==0 or A[0]>x or ((not equal) and A[0]==x):return 0L,R=0,len(A)while R-L>1:C=L+(R-L)//2if A[C]<x or (equal and A[C]==x): L=Celse: R=Creturn L+1def General_Binary_Increase_Search_Integer(L,R,cond,default=None):"""条件式が単調増加であるとき, 整数上で二部探索を行う.L: 解の下限R: 解の上限cond: 条件(1変数関数, 広義単調増加を満たす)default: Lで条件を満たさないときの返り値"""if not(cond(R)): return defaultif cond(L): return LR+=1while R-L>1:C=L+(R-L)//2if cond(C): R=Celse: L=Creturn R#==================================================def check(x,K):A=Floor_Root(x,2)B=Binary_Search_Small_Count(S,x,True)return A+B>=K#==================================================Prime=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]#==================================================T=int(input())Query=[int(input()) for _ in range(T)]M=max(Query)**2#=== 前計算S=set()for p in Prime:for a in range(1,Floor_Root(M,p)+1):S.add(pow(a,p))S=sorted([x for x in S if kth_Power(x,2)==None])for K in Query:print(General_Binary_Increase_Search_Integer(1,M,lambda x:check(x,K),None))