結果

問題 No.2576 LCM Pattern
ユーザー fiblonaria
提出日時 2023-12-09 09:19:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 45 ms / 2,000 ms
コード長 2,135 bytes
コンパイル時間 418 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 57,600 KB
最終ジャッジ日時 2024-09-27 03:31:35
合計ジャッジ時間 2,351 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

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

class mod_int:
"""
.
Attributes:
value (int): .
mod (int): .
"""
def __init__(self, value, mod):
self.value = value % mod
self.mod = mod
def __neg__(self):
return mod_int(-self.value, self.mod)
def __add__(self, other):
if type(other) is mod_int:
return mod_int(self.value + other.value, self.mod)
elif type(other) is int:
return mod_int(self.value + other, self.mod)
raise TypeError()
def __sub__(self, other):
return self + (-other)
def __mul__(self, other):
if type(other) is mod_int:
return mod_int(self.value * other.value, self.mod)
elif type(other) is int:
return mod_int(self.value * other, self.mod)
raise TypeError()
def __truediv__(self, other):
if type(other) in [mod_int, int]:
return self * other ** (self.mod - 2)
raise TypeError()
def __pow__(self, other):
if type(other) is not int:
raise TypeError()
cur, ret = self.value, 1
while other > 0:
if other % 2:
ret = (ret * cur) % self.mod
other //= 2
cur = (cur ** 2) % self.mod
return mod_int(ret, self.mod)
def __repr__(self):
return str(self.value)
def factorize(a):
"""
. O(√a).
Args:
a (int): .
Returns:
list[int]: . a=12[2, 2, 3].
"""
i = 2
ans = []
while i ** 2 <= a:
while a % i == 0:
ans.append(i)
a //= i
i += 1
if a > 1:
ans.append(a)
return ans
N, M = map(int, input().split())
mod = 998244353
ans = mod_int(1, mod)
d = {}
for i in factorize(M):
d[i] = d.get(i, 0) + 1
for v in d:
ans *= mod_int(d[v] + 1, mod) ** N - mod_int(d[v], mod) ** N
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0