結果
| 問題 | No.2829 GCD Divination |
| ユーザー |
 ぬるぽ
|
| 提出日時 | 2024-08-02 22:05:33 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,068 bytes |
| コンパイル時間 | 231 ms |
| コンパイル使用メモリ | 12,672 KB |
| 実行使用メモリ | 19,488 KB |
| 最終ジャッジ日時 | 2024-08-02 22:05:37 |
| 合計ジャッジ時間 | 3,787 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 42 ms
19,488 KB |
| testcase_01 | AC | 41 ms
12,416 KB |
| testcase_02 | TLE | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| 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))