結果
問題 | No.2829 GCD Divination |
ユーザー |
|
提出日時 | 2024-08-02 21:54:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 226 ms / 2,000 ms |
コード長 | 963 bytes |
コンパイル時間 | 267 ms |
コンパイル使用メモリ | 82,156 KB |
実行使用メモリ | 90,368 KB |
最終ジャッジ日時 | 2024-08-02 21:54:45 |
合計ジャッジ時間 | 6,300 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
import collections,sys,math,functools,operator,itertools,bisect,heapq,decimal,string,time,random #sys.setrecursionlimit(10**9) #sys.set_int_max_str_digits(0) #input = sys.stdin.readline def make_divisors(n): lower_divisors , upper_divisors = [], [] i = 1 while i*i <= n: if n % i == 0: lower_divisors.append(i) if i != n // i: upper_divisors.append(n//i) i += 1 return lower_divisors + upper_divisors[::-1] n = int(input()) @functools.lru_cache(maxsize=100000000) def calc(x): if x == 1: return 0 res = 0 div = make_divisors(x) c = collections.defaultdict(int) for i in reversed(div): if i == x: c[x] = 1 continue ans = x//i for j in div: if j % i == 0: ans -= c[j] c[i] = ans res += ans * calc(i) res /= x res += 1 return res / (1 - 1/x) print(calc(n))