結果
問題 | No.2487 Multiple of M |
ユーザー | prin_kemkem |
提出日時 | 2023-09-29 23:47:33 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,891 bytes |
コンパイル時間 | 812 ms |
コンパイル使用メモリ | 87,048 KB |
実行使用メモリ | 81,976 KB |
最終ジャッジ日時 | 2023-09-30 12:52:32 |
合計ジャッジ時間 | 13,256 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 190 ms
81,380 KB |
testcase_01 | AC | 188 ms
81,364 KB |
testcase_02 | AC | 189 ms
81,252 KB |
testcase_03 | AC | 190 ms
81,112 KB |
testcase_04 | WA | - |
testcase_05 | AC | 189 ms
81,136 KB |
testcase_06 | AC | 191 ms
81,260 KB |
testcase_07 | AC | 191 ms
81,228 KB |
testcase_08 | AC | 192 ms
81,024 KB |
testcase_09 | AC | 191 ms
81,260 KB |
testcase_10 | AC | 185 ms
81,260 KB |
testcase_11 | AC | 190 ms
81,568 KB |
testcase_12 | AC | 189 ms
81,608 KB |
testcase_13 | AC | 189 ms
81,476 KB |
testcase_14 | AC | 191 ms
81,512 KB |
testcase_15 | AC | 192 ms
81,284 KB |
testcase_16 | AC | 192 ms
81,676 KB |
testcase_17 | AC | 191 ms
81,248 KB |
testcase_18 | AC | 194 ms
81,392 KB |
testcase_19 | AC | 193 ms
81,488 KB |
testcase_20 | AC | 199 ms
81,540 KB |
testcase_21 | AC | 192 ms
81,044 KB |
testcase_22 | AC | 193 ms
81,208 KB |
testcase_23 | AC | 192 ms
81,032 KB |
testcase_24 | AC | 188 ms
81,340 KB |
testcase_25 | AC | 189 ms
81,412 KB |
testcase_26 | AC | 194 ms
81,592 KB |
testcase_27 | AC | 197 ms
81,436 KB |
testcase_28 | AC | 196 ms
81,668 KB |
testcase_29 | WA | - |
testcase_30 | AC | 190 ms
81,676 KB |
testcase_31 | AC | 195 ms
81,504 KB |
testcase_32 | AC | 194 ms
81,240 KB |
testcase_33 | AC | 197 ms
81,488 KB |
testcase_34 | AC | 190 ms
81,408 KB |
testcase_35 | AC | 194 ms
81,488 KB |
testcase_36 | AC | 189 ms
81,072 KB |
testcase_37 | AC | 192 ms
81,396 KB |
testcase_38 | AC | 187 ms
81,820 KB |
testcase_39 | AC | 195 ms
81,528 KB |
testcase_40 | AC | 193 ms
81,544 KB |
testcase_41 | AC | 191 ms
81,976 KB |
testcase_42 | AC | 192 ms
81,608 KB |
testcase_43 | AC | 190 ms
81,472 KB |
testcase_44 | AC | 192 ms
81,392 KB |
testcase_45 | AC | 188 ms
81,572 KB |
testcase_46 | AC | 192 ms
81,488 KB |
testcase_47 | AC | 191 ms
81,692 KB |
testcase_48 | AC | 193 ms
81,580 KB |
testcase_49 | AC | 190 ms
81,700 KB |
testcase_50 | AC | 193 ms
81,392 KB |
testcase_51 | AC | 191 ms
81,352 KB |
testcase_52 | AC | 192 ms
81,028 KB |
testcase_53 | AC | 191 ms
81,132 KB |
testcase_54 | AC | 192 ms
81,260 KB |
testcase_55 | AC | 193 ms
81,028 KB |
ソースコード
from collections import defaultdict, deque, Counter import copy from itertools import combinations, permutations, product, accumulate, groupby, chain from heapq import heapify, heappop, heappush import math import bisect from pprint import pprint from random import randint import sys # sys.setrecursionlimit(700000) input = lambda: sys.stdin.readline().rstrip('\n') inf = float('inf') mod1 = 10**9+7 mod2 = 998244353 def ceil_div(x, y): return -(-x//y) ################################################# class Matrix(): def __init__(self, mat, mod=None): self.mat = mat self.n = len(mat) self.m = len(mat[0]) self.mod = mod def __mul__(self, other): ret = Matrix([[0]*other.m for _ in range(self.n)], self.mod) for i in range(self.n): for j in range(other.m): for k in range(self.m): ret[i][j] += self.mat[i][k]*other.mat[k][j] if self.mod is not None: ret[i][j] %= self.mod return ret def __add__(self, other): ret = Matrix([[self.mat[i][j] for j in range(self.m)] for i in range(self.n)], self.mod) for i in range(other.n): for j in range(other.m): ret[i][j] += other.mat[i][j] if self.mod is not None: ret[i][j] %= self.mod return ret def __sub__(self, other): ret = Matrix([[self.mat[i][j] for j in range(self.m)] for i in range(self.n)], self.mod) for i in range(other.n): for j in range(other.m): ret[i][j] -= other.mat[i][j] if self.mod is not None: ret[i][j] %= self.mod return ret def __pow__(self, scalar): a = Matrix([[self.mat[i][j] for j in range(self.m)] for i in range(self.n)], self.mod) ret = Matrix.e(self.n, self.mod) while scalar: if scalar&1: ret *= a a *= a scalar >>= 1 return ret def scalar_mul(self, a): ret = Matrix([[self.mat[i][j] for j in range(self.m)] for i in range(self.n)], self.mod) for i in range(self.n): for j in range(self.m): ret[i][j] *= a if self.mod is not None: ret[i][j] %= self.mod return ret def __repr__(self) -> str: return self.mat.__repr__() def __getitem__(self, i): return self.mat[i] def __setitem__(self, i, x): self.mat[i] = x def __len__(self): return len(self.mat) def t(self): return Matrix([list(column) for column in zip(*self.mat)], self.mod) def turn(matrix): if type(matrix) != 'Matrix': return Matrix([list(column) for column in zip(*matrix)]) return Matrix([list(column) for column in zip(*matrix.mat)], matrix.mod) def e(size, mod): return Matrix([[i == j for j in range(size)] for i in range(size)], mod) def prime_factorize(n): ret = defaultdict(int) i = 2 while i*i <= n: if n%i == 0: ret[i] += 1 n //= i else: i += 1 if n != 1: ret[n] += 1 return ret N, M, K = map(int, input().split()) a = Matrix([[0], [1]], mod=mod2) PM, PK = prime_factorize(M), prime_factorize(K) x = 0 s = {} for p, e in PM.items(): if PK[p] == 0: continue s[p] = PK[p] x = max(x, ceil_div(e, PK[p])) i = 0 while i < min(x, N): d = 1 for p, e in s.items(): d *= p**min(PM[p], e*(i+1)) l = M//d if l == 1: print(0) exit() A = Matrix([[d-1, d*(l-1)%mod2], [d, (d-1+d*(l-2))%mod2]], mod=mod2) a = A*a i += 1 if i == N: print(a[0][0]) exit() d = 1 for p, e in s.items(): d *= p**min(PM[p], e*(i+1)) l = M//d if l == 1: print(0) else: A = Matrix([[d-1, d*(l-1)%mod2], [d, (d-1+d*(l-2))%mod2]], mod=mod2) a = A**(N-1-i) * a print(a[0][0])