結果

問題 No.752 mod数列
ユーザー lam6er
提出日時 2025-04-15 22:22:20
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,215 bytes
コンパイル時間 289 ms
コンパイル使用メモリ 81,756 KB
実行使用メモリ 116,928 KB
最終ジャッジ日時 2025-04-15 22:24:57
合計ジャッジ時間 7,743 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 11 WA * 5 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    import sys
    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))
    
    sqrtP = int(math.isqrt(P))
    for L, R in queries:
        L_prime = max(L, 1)
        R_prime = min(R, P)
        if L_prime > R_prime:
            print(0)
            continue
        
        total = P * (R - L + 1)
        sum_n_floor = 0
        
        lower = max(L_prime, 1)
        upper = min(R_prime, sqrtP)
        if lower <= upper:
            for n in range(lower, upper + 1):
                sum_n_floor += n * (P // n)
        
        max_k = sqrtP
        for k in range(1, max_k + 1):
            n_min = (P // (k + 1)) + 1
            n_max = P // k
            a = max(n_min, L_prime)
            b = min(n_max, R_prime)
            a = max(a, sqrtP + 1)
            if a > b:
                continue
            sum_n_floor += k * (a + b) * (b - a + 1) // 2
        
        total -= sum_n_floor
        print(total)

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