結果

問題 No.2487 Multiple of M
ユーザー sotanishysotanishy
提出日時 2023-09-29 23:10:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 41 ms / 2,000 ms
コード長 751 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 54,068 KB
最終ジャッジ日時 2024-07-23 06:50:44
合計ジャッジ時間 3,905 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

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

from math import gcd
import sys
input = sys.stdin.readline
mod = 998244353
N, M, K = map(int, input().split())
def powsum(a, n):
# sum(a**i for i in range(n)) % mod
if n == 1:
return 1
x = powsum(a**2 % mod, n//2)
res = x + a * x
if n % 2 == 1:
res += pow(a, n-1, mod)
return res % mod
def f(n, i):
# use n terms to make a multiple of M/gcd(M,K**i)
g = gcd(M, K**i)
if n == 0:
return 1
if n == 1:
return g-1
if i > 30:
g = gcd(M, K**30)
if n % 2 == 0:
return (-g * powsum(1-M, n) + 1) % mod
else:
return (-g * (M-1) * powsum(1-M, n-1) + g - 1) % mod
return (pow(M-1, n-1, mod)*g - f(n-1, i+1)) % mod
print(f(N, 0))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0