結果

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

ソースコード

diff # 

import math

def sum_floor_times_n(a, b, P):
    if a > b:
        return 0
    sum_total = 0
    sqrt_p = int(math.isqrt(P))
    
    # 处理k <= sqrt_p的情况
    for k in range(1, sqrt_p + 1):
        low = P // (k + 1) + 1
        high = P // k
        if high > b:
            high = b
        if low < a:
            low = a
        if low > high:
            continue
        # 计算sum n from low to high
        s = (high * (high + 1) // 2) - ((low - 1) * low // 2)
        sum_total += k * s
    
    # 处理k > sqrt_p的情况，此时n <= sqrt_p
    max_n = min(sqrt_p, b)
    for n in range(a, max_n + 1):
        k = P // n
        if k > sqrt_p:
            sum_total += k * 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
        a = max(L, 1)
        b = min(R, P)
        sum_r = sum_floor_times_n(1, b, P)
        sum_l_1 = sum_floor_times_n(1, L-1, P) if L > 1 else 0
        total = sum_r - sum_l_1
        ans = P * (R - L + 1) - total
        print(ans)

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