結果

問題 No.1260 たくさんの多項式
ユーザー lam6er
提出日時 2025-03-31 17:28:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 182 ms / 2,000 ms
コード長 1,028 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 82,604 KB
実行使用メモリ 76,168 KB
最終ジャッジ日時 2025-03-31 17:28:25
合計ジャッジ時間 8,248 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    N = int(input())
    M = int(N ** 0.5)
    total = 0

    # Process small i (i <= M)
    for i in range(2, M + 1):
        n = N
        s = 0
        while n > 0:
            n, d = divmod(n, i)
            s += d
        total = (total + s) % MOD

    # Process large i (i > M)
    max_k = N // (M + 1)
    for k in range(1, max_k + 1):
        L = (N // (k + 1)) + 1
        R = N // k
        L = max(L, M + 1)
        if R < L:
            continue
        cnt = R - L + 1
        # Calculate term1 = N * cnt
        term1 = (N % MOD) * cnt % MOD
        # Calculate sum_x = sum (i-1 for i in L..R) = sum from (L-1) to (R-1)
        a = R - 1
        b = L - 2
        if b < 0:
            sum_x = a * (a + 1) // 2
        else:
            sum_x = (a * (a + 1) // 2) - (b * (b + 1) // 2)
        term2 = (k % MOD) * (sum_x % MOD) % MOD
        contribution = (term1 - term2) % MOD
        total = (total + contribution) % MOD

    print(total % MOD)

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