結果

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

ソースコード

diff # 

import sys
import math

def main():
    input = sys.stdin.read().split()
    idx = 0
    P = int(input[idx])
    idx += 1
    Q = int(input[idx])
    idx += 1
    queries = []
    for _ in range(Q):
        L = int(input[idx])
        R = int(input[idx+1])
        queries.append((L, R))
        idx += 2
    
    K = int(math.isqrt(P))
    
    for L, R in queries:
        L_prime = max(L, 1)
        R_prime = min(R, P)
        if L_prime > R_prime:
            total = 0
        else:
            sum_small = 0
            for k in range(1, K + 1):
                m = (P // (k + 1)) + 1
                M = P // k
                a = max(m, L_prime)
                b = min(M, R_prime)
                if a > b:
                    continue
                count = b - a + 1
                sum_n = (a + b) * count // 2
                sum_small += k * sum_n
            
            sum_large = 0
            a = max(L_prime, 1)
            b = min(R_prime, K)
            if a <= b:
                for n in range(a, b + 1):
                    k = P // n
                    if k > K:
                        sum_large += n * k
            
            total = sum_small + sum_large
        
        result = (R - L + 1) * P - total
        print(result)

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