結果

問題 No.752 mod数列
ユーザー lam6er
提出日時 2025-04-15 22:33:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,157 bytes
コンパイル時間 237 ms
コンパイル使用メモリ 81,784 KB
実行使用メモリ 107,448 KB
最終ジャッジ日時 2025-04-15 22:35:53
合計ジャッジ時間 9,185 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 16 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

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])
        R = int(input[ptr + 1])
        queries.append((L, R))
        ptr += 2
    
    K = int(P ** 0.5)
    for L, R in queries:
        total = 0
        
        # Part 1: q <= K
        for q in range(1, K + 1):
            start = (P // (q + 1)) + 1
            end = P // q
            a = max(L, start)
            b = min(R, end)
            if a > b:
                continue
            cnt = b - a + 1
            total += q * (a + b) * cnt // 2
        
        # Part 2: n <= P // (K + 1)
        a = max(L, 1)
        b = min(R, P // (K + 1))
        if a <= b:
            # Compute sum(n * (P // n) for n in [a, b] if (P//n) > K)
            sum_part = 0
            for n in range(a, b + 1):
                q_n = P // n
                if q_n > K:
                    sum_part += n * q_n
            total += sum_part
        
        res = P * (R - L + 1) - total
        print(res)

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