結果

問題 No.752 mod数列
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:07:34
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,382 bytes
コンパイル時間 432 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 98,428 KB
最終ジャッジ日時 2025-06-12 21:09:24
合計ジャッジ時間 14,965 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 14 TLE * 3 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def compute_sum(X, P):
    if X == 0:
        return 0
    sum_total = 0
    k_max = int(math.isqrt(P))
    if X <= k_max:
        for n in range(1, X + 1):
            sum_total += n * (P // n)
    else:
        for n in range(1, k_max + 1):
            sum_total += n * (P // n)
        max_k = P // (k_max + 1)
        for k in range(1, max_k + 1):
            m = (P // (k + 1)) + 1
            m_prime = P // k
            start = max(m, k_max + 1)
            end = min(m_prime, X)
            if start > end:
                continue
            count = end - start + 1
            sum_n = (start + end) * count // 2
            sum_total += k * sum_n
    return sum_total

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    P = int(input[ptr])
    ptr += 1
    Q = int(input[ptr])
    ptr += 1
    for _ in range(Q):
        L = int(input[ptr])
        ptr += 1
        R = int(input[ptr])
        ptr += 1
        if R > P:
            part1 = compute_sum(P, P)
            part2 = compute_sum(L-1, P)
            sum_total = part1 - part2
            sum_mod = (R - L + 1) * P - sum_total
        else:
            part1 = compute_sum(R, P)
            part2 = compute_sum(L-1, P)
            sum_total = part1 - part2
            sum_mod = (R - L + 1) * P - sum_total
        print(sum_mod)

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