結果
| 問題 | No.2829 GCD Divination |
| ユーザー |
 ぬるぽ
|
| 提出日時 | 2024-08-03 09:00:42 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,068 bytes |
| コンパイル時間 | 450 ms |
| コンパイル使用メモリ | 82,072 KB |
| 実行使用メモリ | 98,596 KB |
| 最終ジャッジ日時 | 2024-08-03 09:00:50 |
| 合計ジャッジ時間 | 7,317 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 149 ms
98,016 KB |
| testcase_01 | AC | 149 ms
90,984 KB |
| testcase_02 | TLE | - |
| testcase_03 | AC | 150 ms
91,100 KB |
| testcase_04 | TLE | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
ソースコード
from copy import deepcopy, copy
import sys
import io
from typing import Optional
import time
from random import randrange, randint, random, uniform
import sys, io
from collections import deque, defaultdict
import heapq
from collections import Counter
import math
from math import gcd
from functools import lru_cache
from itertools import combinations, permutations
from bisect import bisect_left, bisect_right
from itertools import groupby
from itertools import accumulate
from math import factorial
import decimal
import math
# from sortedcontainers import SortedList
# import pypyjit
# pypyjit.set_param("max_unroll_recursion=-1")
sys.setrecursionlimit(1000000000)
sys.set_int_max_str_digits(1000000000)
start_time = time.time()
N = int(input())
@lru_cache(maxsize=None)
def rec(n):
if n == 1:
return 0
num = 0
cnt = 0
for M in range(1, n + 1):
if gcd(n, M) == n:
cnt += 1
continue
num += rec(gcd(n, M))
num += n
# print(n, cnt)
return num * 1 / (n - cnt)
print(rec(N))