結果
問題 | No.2318 Phys Bone Maker |
ユーザー |
|
提出日時 | 2023-05-27 01:22:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,915 ms / 3,000 ms |
コード長 | 1,144 bytes |
コンパイル時間 | 538 ms |
コンパイル使用メモリ | 81,664 KB |
実行使用メモリ | 79,616 KB |
最終ジャッジ日時 | 2024-12-25 12:47:54 |
合計ジャッジ時間 | 19,914 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
def make_divisors(n):lower_divisors , upper_divisors = [], []i = 1while i*i <= n:if n % i == 0:lower_divisors.append(i)if i != n // i:upper_divisors.append(n//i)i += 1return lower_divisors + upper_divisors[::-1]def factorization(n):arr = dict()temp = nfor i in range(2, int(-(-n**0.5//1))+1):if temp%i==0:cnt=0while temp%i==0:cnt+=1temp //= iarr[i]=cntif temp!=1:arr[temp]=1if len(arr)==0:arr[n]=1return arrMOD = 998244353N = int(input())Y = make_divisors(N)F = []for y in Y:F.append(factorization(y))dp = [0 for _ in range(len(Y))]dp[0] = 1for i in range(len((Y))):for j in range(i+1, len(Y)):#Y[i] -> Y[j]if Y[j]%Y[i]!=0:continuetemp = dp[i]for p in F[i]:if p==1:continueej = F[j][p]ei = F[i][p]if ei==ej:temp=temp*(ej+1)%MODdp[j] = (dp[j]+temp)%MODprint(dp[-1])