結果

問題 No.2829 GCD Divination
コンテスト
ユーザー Sinonen
提出日時 2025-02-02 10:01:06
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,112 bytes
コンパイル時間 1,948 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 243,328 KB
最終ジャッジ日時 2025-02-02 10:02:59
合計ジャッジ時間 112,571 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

# N の最大値
MAX_N = 10**7

# トーシェント関数の計算
def compute_totients(limit):
    phi = list(range(limit + 1))
    for i in range(2, limit + 1):
        if phi[i] == i:  # i は素数
            for j in range(i, limit + 1, i):
                phi[j] -= phi[j] // i
    return phi

# 期待値の計算
def compute_expected_values(limit):
    phi = compute_totients(limit)
    E = [0.0] * (limit + 1)  # E[1] = 0 は初期化済み

    for n in range(2, limit + 1):
        sum_E = 0.0
        # n の約数ごとに集計
        d = 1
        while d * d <= n:
            if n % d == 0:
                d1, d2 = d, n // d
                sum_E += phi[n // d1] * E[d1]
                if d1 != d2:
                    sum_E += phi[n // d2] * E[d2]
            d += 1

        E[n] = 1 + sum_E / n
    
    return E

# 事前計算
E_values = compute_expected_values(MAX_N)

# メイン処理
def main():
    N = int(sys.stdin.readline())  # N を受け取る
    print(f"{E_values[N]:.10f}")   # 小数点以下10桁で出力

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