結果

問題 No.1573 Divisor Function
ユーザー LyricalMaestro
提出日時 2024-12-29 18:41:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,479 bytes
コンパイル時間 240 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 68,864 KB
最終ジャッジ日時 2024-12-29 18:41:20
合計ジャッジ時間 8,640 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 36 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff #

## https://yukicoder.me/problems/no/1601

import math

MOD = 998244353

def main():
    N, M = map(int, input().split())

    sqrt_m = int(math.sqrt(M))

    # i <= sqrt_mの場合
    answer = 0
    for i in range(1, sqrt_m + 1):
        l = N // i

        ans1 = (l * i) % MOD
        ans2 = (l * (l + 1)) % MOD
        ans2 *= pow(2, MOD - 2, MOD)
        ans2 %= MOD
        ans2 *= i
        ans2 %= MOD
        ans = (ans1 + ans2) % MOD
        ans %= MOD
        answer += ans
        answer %= MOD

    # i > sqrt_mの場合
    if sqrt_m < N:
        b_flg = False
        upper = float("inf")
        lower = N
        for l in range(M + 1):

            u0 = min(upper, M)
            l0 = min(lower, M)

#            print(f"l = {l}, u0 = {u0}, l0 = {l0}")

            ans1 = (u0 * (u0 + 1)) % MOD
            ans1 *= pow(2, MOD - 2, MOD)
            ans1 %= MOD
            ans2 = (l0 * (l0 + 1)) % MOD
            ans2 *= pow(2, MOD - 2, MOD)
            ans2 %= MOD

            x = (l * (l + 1)) % MOD
            x *= pow(2, MOD - 2, MOD)
            x %= MOD

            ans = (ans1 - ans2) % MOD
            ans *= (x + l)
            ans %= MOD

            answer += ans
            answer %= MOD
#            print(answer , ans)

            if b_flg:
                break

            upper = lower
            lower = N // (l + 2)
            if lower <= sqrt_m:
                b_flg = True

    print(answer)



if __name__ == "__main__":
    main()
0