結果

問題 No.752 mod数列
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:22:35
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,336 bytes
コンパイル時間 331 ms
コンパイル使用メモリ 82,112 KB
実行使用メモリ 99,200 KB
最終ジャッジ日時 2025-03-31 17:23:26
合計ジャッジ時間 7,228 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    
    for _ in range(Q):
        L = int(input[ptr])
        ptr += 1
        R = int(input[ptr])
        ptr += 1
        
        valid_R = min(R, P)
        if L > valid_R:
            ans = P * (R - L + 1)
        else:
            sum_part = 0
            n_current = L
            valid_R_val = valid_R
            while n_current <= valid_R_val:
                v = P // n_current
                n_end = P // v
                if n_end > valid_R_val:
                    n_end = valid_R_val
                
                # Determine the current block's range [low, high]
                low = (P // (v + 1)) + 1
                low = max(low, L)
                high = min(n_end, valid_R_val)
                
                if low > high:
                    n_current = high + 1
                    continue
                
                # Calculate contribution of this block
                count = high - low + 1
                total_n = (low + high) * count // 2
                sum_part += v * total_n
                n_current = high + 1
            
            ans = P * (R - L + 1) - sum_part
        
        print(ans)

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