#1015905 (PyPy3) No.2891 Mint

• 問題: No.2891 Mint
• ユーザー: LyricalMaestro
• 提出日時: 2024-10-06 23:06:36
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 138 ms / 2,000 ms
• コード長: 1,895 bytes
• コンパイル時間: 154 ms
• コンパイル使用メモリ: 82,484 KB
• 実行使用メモリ: 61,824 KB
• 最終ジャッジ日時: 2024-10-06 23:06:43
• 合計ジャッジ時間: 5,743 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 54

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
## https://yukicoder.me/problems/no/1385
import math
MOD = 998244353
inv2 = pow(2, MOD - 2, MOD)
def sum_k(n):
    ans = (n * (n + 1)) % MOD
    ans *= inv2
    ans %= MOD
    return ans
def solve_normal(N, M):
    answer = 0
    for k in range(1, N + 1):
        n = (M % k)
        answer += n
        answer %= MOD
    return answer
def solve_true(N, M):
    sqrt_n = int(math.sqrt(M))
    # 前半は正規に解く
    answer1 = 0
    for k in range(1, min(N, sqrt_n) + 1):
        n = (M % k)
        answer1 += n
        answer1 %= MOD
    # 後半は商に注目
    start = N
    answer2 = 0
    for q in range(sqrt_n + 1):
        end = M // (q + 1)
        end = max(sqrt_n, end)
        if start > end:
            # [start, end)が商qの範囲
            if q == 0:
                n1 = (N - M) % MOD
                ans = (n1 * M) % MOD
                answer2 += ans
                answer2 %= MOD
            else:
                init_s = M // q
                init_r = M % q
                a1 = (-q * sum_k(start)) % MOD
                b1 = (init_s * q) % MOD
                b1 += init_r
                b1 %= MOD
                b1 *= start
                b1 %= MOD
                a2 = (-q * sum_k(end)) % MOD
                b2 = (init_s * q) % MOD
                b2 += init_r
                b2 %= MOD
                b2 *= end
                b2 %= MOD
                ans = (a1 -a2) % MOD
                ans += b1
                ans %= MOD
                ans -= b2
                ans %= MOD
                answer2 += ans
                answer2 %= MOD
            start = end
        if end == sqrt_n:
            break
    return (answer1 + answer2) % MOD
def main():
    N, M = map(int, input().split())
#    ans1 = solve_normal(N, M)
    ans2 = solve_true(N, M)
#    print(ans1)
    print(ans2)
if __name__ == "__main__":
    main()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX