結果

問題 No.752 mod数列
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:13:31
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,462 bytes
コンパイル時間 239 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 109,904 KB
最終ジャッジ日時 2025-06-12 16:13:43
合計ジャッジ時間 8,190 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 17 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    input = sys.stdin.read().split()
    ptr = 0
    P = int(input[ptr])
    ptr += 1
    Q = int(input[ptr])
    ptr += 1

    queries = []
    for _ in range(Q):
        L = int(input[ptr])
        ptr += 1
        R = int(input[ptr])
        ptr += 1
        queries.append((L, R))

    D = int(math.isqrt(P))
    # Precompute sum_A: sum_A[x] is sum_{n=1 to x} n * floor(P / n)
    sum_A = [0] * (D + 1)
    for n in range(1, D + 1):
        k = P // n
        sum_A[n] = sum_A[n-1] + n * k

    for L, R in queries:
        # Compute A: sum n*floor(P/n) for n <= D and in [L, R]
        A = 0
        if L <= D:
            upper = min(R, D)
            if L == 1:
                a_sum = sum_A[upper]
            else:
                a_sum = sum_A[upper] - sum_A[L-1]
            A = a_sum

        # Compute B: sum n*floor(P/n) for n > D and in [L, R]
        lower = max(L, D + 1)
        if lower > R:
            B = 0
        else:
            B = 0
            for k in range(1, D + 1):
                n_low = (P // (k + 1)) + 1
                n_high = P // k
                a = max(n_low, lower)
                b = min(n_high, R)
                if a > b:
                    continue
                count = b - a + 1
                sum_n = (a + b) * count // 2
                B += k * sum_n

        S = A + B
        total = P * (R - L + 1) - S
        print(total)

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