結果
問題 | No.2891 Mint |
ユーザー |
|
提出日時 | 2024-09-13 23:00:56 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 907 bytes |
コンパイル時間 | 306 ms |
コンパイル使用メモリ | 82,380 KB |
実行使用メモリ | 136,028 KB |
最終ジャッジ日時 | 2024-09-13 23:01:03 |
合計ジャッジ時間 | 5,204 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 WA * 9 |
ソースコード
def isqrt(n): if n == 0: return 0 x = 1 << (n.bit_length() + 1) // 2 y = (x + n // x) // 2 while y < x: x = y y = (x + n // x) // 2 return x import sys input = sys.stdin.readline MOD = 998244353 N, M = map(int, input().split()) dp = N*M%MOD if N<=isqrt(M) or N<=10**6: for i in range(1, N+1): cnt = M//i dp -= i*cnt%MOD dp %= MOD print(dp) else: dp = N*M%MOD tmp = [] for i in range(1, isqrt(M)+1): cnt = M//i tmp.append(cnt) dp -= i*cnt%MOD dp %= MOD #print(tmp) for i in range(len(tmp)-1): cnt = min(tmp[i], N)-tmp[i+1] st = tmp[i+1]+1 if cnt>0: dp -= (i+1)*((st+st+cnt-1)*cnt//2)%MOD dp %= MOD cnt = tmp[-1]-len(tmp) st = len(tmp) if cnt>0: dp -= len(tmp)*((st+st+cnt-1)*cnt//2)%MOD dp %= MOD print(dp)