結果

問題 No.752 mod数列
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:04:12
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,602 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 99,072 KB
最終ジャッジ日時 2025-06-12 13:09:39
合計ジャッジ時間 8,638 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 11 WA * 5 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

    K = int(math.isqrt(P)) if P > 0 else 0

    for _ in range(Q):
        L = int(input[ptr])
        ptr += 1
        R = int(input[ptr])
        ptr += 1

        # Adjust R if it's larger than P
        R_orig = R
        R = min(R, P)
        if L > R:
            print(0)
            continue

        total = P * (R - L + 1)
        S = 0

        # Part a: q from 1 to K
        for q in range(1, K + 1):
            a = (P // (q + 1)) + 1
            b = P // q
            a = max(a, L)
            b = min(b, R)
            if a > b:
                continue
            count = b - a + 1
            sum_n = (a + b) * count // 2
            S += q * sum_n

        # Part b: n from 1 to K
        for n in range(1, K + 1):
            if n < L or n > R:
                continue
            q = P // n
            if q <= K:
                continue
            S += n * q

        # Handle the case where R_orig > P
        if R_orig > P:
            # Add terms from P+1 to R_orig
            # Each term is P mod n = P (since n > P)
            # But P mod n = P - n * 0 = P
            # But wait, no. For n > P, P mod n = P
            # So sum from max(L, P+1) to R_orig of P
            lower = max(L, P + 1)
            upper = R_orig
            if lower <= upper:
                cnt = upper - lower + 1
                total += P * cnt

        ans = total - S
        print(ans)

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