結果

問題 No.2318 Phys Bone Maker
ユーザー FromBooskaFromBooska
提出日時 2023-05-27 13:50:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,967 ms / 3,000 ms
コード長 1,781 bytes
コンパイル時間 690 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 79,616 KB
最終ジャッジ日時 2024-12-25 23:13:46
合計ジャッジ時間 20,962 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

# Ndp
#
# https://yukicoder.me/submissions/872922
N = int(input())
def divisors(n):
lower_divisors , upper_divisors = [], []
i = 1
while i*i <= n:
if n % i == 0:
lower_divisors.append(i)
if i != n // i:
upper_divisors.append(n//i)
i += 1
return lower_divisors + upper_divisors[::-1]
def factorization_dic(n): #
arr = {}
temp = n
for i in range(2, int(-(-n**0.5//1))+1):
if temp%i==0:
cnt=0
while temp%i==0:
cnt+=1
temp //= i
arr[i] = cnt
if temp!=1:
arr[temp] = 1
if arr==[]:
arr[n] = 1
return arr
N_divs = divisors(N)
L = len(N_divs)
all_factors = []
for d in N_divs:
all_factors.append(factorization_dic(d))
#print(all_factors)
mod = 998244353
# N1
# dp[i]
dp = [0]*L
dp[0] = 1
for i in range(L):
for j in range(i+1, L):
if N_divs[j]%N_divs[i] != 0:
continue
temp = dp[i]
for p in all_factors[i]:
if p == 1:
continue
p_count_current = all_factors[i][p]
p_count_new = all_factors[j][p]
if p_count_current == p_count_new:
#
#print('i', i, 'j', j, 'p', p, p_count_current, p_count_new)
temp *= p_count_new+1
temp %= mod
dp[j] += temp
dp[j] %= mod
ans = dp[L-1]%mod
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0