結果
問題 | No.2798 Multiple Chain |
ユーザー |
|
提出日時 | 2024-06-28 23:14:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 87 ms / 2,000 ms |
コード長 | 1,148 bytes |
コンパイル時間 | 188 ms |
コンパイル使用メモリ | 82,420 KB |
実行使用メモリ | 67,712 KB |
最終ジャッジ日時 | 2024-06-28 23:14:43 |
合計ジャッジ時間 | 4,956 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
N=int(input()) V=[0,0] for K in range(2,70): dp=[] for j in range(K+1): dp.append([0]*(K+1)) for j in range(1,K+1): dp[j][K-j]=1 for j in range(K,0,-1): for k in range(K,0,-1): #print(j,k) if dp[j][k]==0: continue for l in range(1,j+1): #print(l,j,k) if k-l<0: break #print(l,j,k) dp[l][k-l]+=dp[j][k] #print(dp) cnt=0 #print(dp) for i in range(1,K+1): cnt+=dp[i][0] V.append(cnt) def fact(M): C=[] for i in range(2,10**6+1): if i==1: break if M%i==0: cnt=0 while M%i==0: M=M//i cnt+=1 if cnt>=2: C.append((i,cnt)) if C==[] and M==1: return 1 elif C==[]: H=int(M**0.5) ok=0 for i in range(H-3,H+5): if i**2==M: return 2 return 1 else: if M==1: return C else: H=int(M**0.5) ok=0 for i in range(H-3,H+5): if i**2==M: C.append((i,2)) return C C=fact(N) #print(V) #print(type(5)==int) if type(C)==int: print(C) else: ans=1 for i in range(len(C)): ans=ans*V[C[i][1]] print(ans)