結果
問題 | No.2487 Multiple of M |
ユーザー | prin_kemkem |
提出日時 | 2023-09-29 23:50:31 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,895 bytes |
コンパイル時間 | 281 ms |
コンパイル使用メモリ | 87,228 KB |
実行使用メモリ | 82,052 KB |
最終ジャッジ日時 | 2023-09-30 12:52:31 |
合計ジャッジ時間 | 12,068 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 178 ms
81,228 KB |
testcase_01 | AC | 172 ms
80,996 KB |
testcase_02 | AC | 174 ms
81,536 KB |
testcase_03 | AC | 174 ms
81,348 KB |
testcase_04 | AC | 173 ms
81,416 KB |
testcase_05 | AC | 172 ms
81,200 KB |
testcase_06 | AC | 177 ms
81,264 KB |
testcase_07 | AC | 176 ms
81,004 KB |
testcase_08 | AC | 176 ms
81,540 KB |
testcase_09 | AC | 175 ms
81,068 KB |
testcase_10 | AC | 175 ms
81,432 KB |
testcase_11 | AC | 174 ms
81,556 KB |
testcase_12 | AC | 176 ms
81,588 KB |
testcase_13 | AC | 177 ms
81,748 KB |
testcase_14 | AC | 173 ms
81,740 KB |
testcase_15 | AC | 178 ms
81,660 KB |
testcase_16 | AC | 175 ms
81,552 KB |
testcase_17 | AC | 172 ms
81,204 KB |
testcase_18 | AC | 174 ms
81,444 KB |
testcase_19 | AC | 176 ms
81,504 KB |
testcase_20 | AC | 176 ms
81,644 KB |
testcase_21 | AC | 182 ms
81,052 KB |
testcase_22 | AC | 182 ms
81,200 KB |
testcase_23 | AC | 177 ms
81,296 KB |
testcase_24 | AC | 175 ms
81,300 KB |
testcase_25 | AC | 176 ms
81,444 KB |
testcase_26 | AC | 175 ms
81,576 KB |
testcase_27 | AC | 175 ms
81,536 KB |
testcase_28 | AC | 178 ms
81,496 KB |
testcase_29 | WA | - |
testcase_30 | AC | 175 ms
81,592 KB |
testcase_31 | AC | 174 ms
81,540 KB |
testcase_32 | AC | 172 ms
81,188 KB |
testcase_33 | AC | 175 ms
81,488 KB |
testcase_34 | AC | 176 ms
81,572 KB |
testcase_35 | AC | 175 ms
81,624 KB |
testcase_36 | AC | 173 ms
81,304 KB |
testcase_37 | AC | 175 ms
81,556 KB |
testcase_38 | AC | 175 ms
81,640 KB |
testcase_39 | AC | 176 ms
81,488 KB |
testcase_40 | AC | 177 ms
81,440 KB |
testcase_41 | AC | 178 ms
82,052 KB |
testcase_42 | AC | 174 ms
81,660 KB |
testcase_43 | AC | 177 ms
81,912 KB |
testcase_44 | AC | 176 ms
81,640 KB |
testcase_45 | AC | 175 ms
81,896 KB |
testcase_46 | AC | 172 ms
81,664 KB |
testcase_47 | AC | 172 ms
81,672 KB |
testcase_48 | AC | 172 ms
81,616 KB |
testcase_49 | AC | 174 ms
81,600 KB |
testcase_50 | AC | 177 ms
81,668 KB |
testcase_51 | AC | 171 ms
81,116 KB |
testcase_52 | AC | 174 ms
81,392 KB |
testcase_53 | AC | 176 ms
81,172 KB |
testcase_54 | AC | 173 ms
81,312 KB |
testcase_55 | AC | 170 ms
81,204 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-1): 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-1: 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])