結果
問題 | No.1006 Share an Integer |
ユーザー |
👑 ![]() |
提出日時 | 2021-02-19 20:12:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 665 ms / 2,000 ms |
コード長 | 1,266 bytes |
コンパイル時間 | 341 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 108,160 KB |
最終ジャッジ日時 | 2024-09-16 16:08:59 |
合計ジャッジ時間 | 7,733 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
def Smallest_Prime_Factor(N):"""0,1,2,...,Nの最小の素因数のリスト(0,1については1にしている)"""if N==0:return [1]N=abs(N)L=list(range(N+1))L[0]=L[1]=1x=4while x<=N:L[x]=2x+=2x=9while x<=N:if L[x]==x:L[x]=3x+=6x=5Flag=Truewhile x*x<=N:if L[x]==x:y=x*xwhile y<=N:if L[y]==y:L[y]=xy+=x<<1x+=2 if Flag else 4return Ldef Faster_Prime_Factorization(N,L):"""L:Smallest_Prime_Factors(N)で求めたリスト"""N=abs(N)D=[]while N>1:a=L[N]k=0while L[N]==a:k+=1N//=aD.append([a,k])return D#================================================import syswrite=sys.stdout.writeX=int(input())L=Smallest_Prime_Factor(X)f=[0]*(X+1)for x in range(1,X+1):T=Faster_Prime_Factorization(x,L)m=1for p,e in T:m*=e+1f[x]=x-mMin=float("inf")for A in range(1,X):B=X-AMin=min(Min,abs(f[A]-f[B]))for A in range(1,X):B=X-Aif abs(f[A]-f[B])==Min:write("{} {}\n".format(A,B))