結果
| 問題 | No.2829 GCD Divination |
| ユーザー |
 ぬるぽ
|
| 提出日時 | 2024-08-02 22:03:41 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,068 bytes |
| コンパイル時間 | 215 ms |
| コンパイル使用メモリ | 82,568 KB |
| 実行使用メモリ | 98,744 KB |
| 最終ジャッジ日時 | 2024-08-02 22:03:48 |
| 合計ジャッジ時間 | 6,242 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 130 ms
98,012 KB |
| testcase_01 | AC | 131 ms
91,028 KB |
| testcase_02 | AC | 1,997 ms
91,656 KB |
| testcase_03 | AC | 126 ms
90,820 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))