結果
問題 | No.2829 GCD Divination |
ユーザー |
|
提出日時 | 2024-08-02 22:50:03 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 192 ms / 2,000 ms |
コード長 | 849 bytes |
コンパイル時間 | 324 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 11,776 KB |
最終ジャッジ日時 | 2024-08-02 22:50:07 |
合計ジャッジ時間 | 3,674 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
from collections import defaultdict from fractions import Fraction def divisors(n): D = {1, n} i = 2 while i*i <= n: if n % i == 0: D.add(i) D.add(n//i) i += 1 return D def factors(n): D = defaultdict(int) i = 2 while i*i <= n: if n % i == 0: D[i] += 1 n //= i else: i += 1 if n > 1: D[n] += 1 return D def euler(n): e = n F = factors(n) for p in F: e = e*(p-1)//p return e memo = {1: Fraction(0)} def expected(n): if n in memo: return memo[n] D = divisors(n) e = Fraction(1) for d in D: if d < n: e += Fraction(euler(n//d), n) * expected(d) memo[n] = e * Fraction(n, n-1) return memo[n] print(float(expected(int(input()))))