結果

問題 No.1260 たくさんの多項式
コンテスト
ユーザー LyricalMaestro
提出日時 2026-08-10 00:39:50
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 364 ms / 2,000 ms
+ 649µs
コード長 1,055 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 243 ms
コンパイル使用メモリ 95,592 KB
実行使用メモリ 83,712 KB
最終ジャッジ日時 2026-08-10 00:40:06
合計ジャッジ時間 14,934 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 61
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/1260

import math

MOD = 10 ** 9 + 7

def main():
    N = int(input())

    sqrt_n = int(math.sqrt(N))

    answer = 0
    for i in range(2, sqrt_n + 1):
        n = N
        ans  =0
        while n > 0:
            ans += n % i
            n //= i
        ans %= MOD
        answer += ans
        answer %= MOD

    for q in range(1, sqrt_n + 1):
        # (lower, upper]で考える
        upper  = N // q
        if upper <= sqrt_n:
            continue

        lower = N // (q + 1)
        lower = max(sqrt_n, lower)
        if lower >= upper:
            continue


        count = upper - lower
        ans1 = (q * count) % MOD

        b = N - upper * q
        ans2 = ((b - q) * count) %MOD
        ans3 = (count * (count + 1)) % MOD
        ans3 *= pow(2, MOD - 2, MOD)
        ans3 %= MOD
        ans3 *= q
        ans3 %= MOD

        ans = (ans1 + ans2) % MOD
        ans += ans3
        ans %= MOD
        answer += ans
        answer %= MOD
    print(answer)






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