結果
問題 | No.2576 LCM Pattern |
ユーザー |
|
提出日時 | 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 |
ソースコード
class mod_int:"""有限体上の整数有限体上の整数とその演算を扱うクラスです.Attributes:value (int): 整数の値.mod (int): 有限体の法."""def __init__(self, value, mod):self.value = value % modself.mod = moddef __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, 1while other > 0:if other % 2:ret = (ret * cur) % self.modother //= 2cur = (cur ** 2) % self.modreturn 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 = 2ans = []while i ** 2 <= a:while a % i == 0:ans.append(i)a //= ii += 1if a > 1:ans.append(a)return ansN, M = map(int, input().split())mod = 998244353ans = mod_int(1, mod)d = {}for i in factorize(M):d[i] = d.get(i, 0) + 1for v in d:ans *= mod_int(d[v] + 1, mod) ** N - mod_int(d[v], mod) ** Nprint(ans)