結果

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

ソースコード

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))
    
    K = int(math.isqrt(P))
    
    for L, R in queries:
        sum_total = 0
        
        # 处理 d <= K 的情况
        d_max = P // L if L != 0 else 0
        for d in range(1, K +1):
            lower = (P // (d +1)) + 1
            upper = P // d
            lower = max(L, lower)
            upper = min(R, upper)
            if lower > upper:
                continue
            count = upper - lower +1
            sum_n = (lower + upper) * count // 2
            sum_total += d * sum_n
        
        # 处理 n <= K 的情况，此时 d = P //n 可能大于 K
        n_start = max(L, 1)
        n_end = min(R, K)
        for n in range(n_start, n_end +1):
            d = P // n
            if d > K:
                sum_total += n * d
        
        # 计算最终结果
        total_mod = P * (R - L +1) - sum_total
        print(total_mod)
    
if __name__ == '__main__':
    main()
0