結果

問題 No.2645 Sum of Divisors?
コンテスト
ユーザー tassei903
提出日時 2025-04-11 16:42:35
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,400 bytes
コンパイル時間 331 ms
コンパイル使用メモリ 82,204 KB
実行使用メモリ 581,376 KB
最終ジャッジ日時 2025-04-11 16:42:57
合計ジャッジ時間 19,033 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 MLE * 1
other AC * 26 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################

# (x, y) がvalid か
# a_i ** 2 <= x となる最大の i を取ってきて
# a_i ** 2 <= x < (a_i + 1) ** 2
# a_i <= floor(sqrt(x))
# 8.1 * 10 ** 17
# x * y = z * wとなる validな(z, w)が存在するか

# sum_i sum_(j | i) 1/i
# sum_j 1/j sum_{i <= floor(n / j)} 1/i
# sum_j 1/j H(floor(n/j))
# sum_{l, r, k} * H(k) * {H(r) - H(l)}
def floor_decomposition(x): # k = floor(x / i) (L < i <= R) となる (k, L, R) のリストを返す
    res = []
    R = x
    while R:
        q = x // R
        L = x // (q + 1)
        res.append((q, L, R))
        R = L
    return res


n = ni()
ans = 0

N = 2 * 10 ** 7 
hh = [0] * (N + 1)
for i in range(N):
    hh[i+1] = 1/(i + 1) + hh[i]

from math import log
phi = 0.5772156649015328606

# for i in range(1, n+1):
#     print(i, h[i], log(i) + 1/(2 * n) + phi,h[i] - (log(i) + 1/(2 * n) + phi))
def h(i):
    if i == 0:
        return 0 
    if i <= N:
        return hh[i]
    return log(i) + 1 / (2 * n) + phi

for k, l, r in floor_decomposition(n):
    ans += h(k) * (h(r) - h(l))

print(ans)
0