結果
問題 | No.2829 GCD Divination |
ユーザー | ぬるぽ |
提出日時 | 2024-08-03 09:25:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 302 ms / 2,000 ms |
コード長 | 1,745 bytes |
コンパイル時間 | 350 ms |
コンパイル使用メモリ | 82,320 KB |
実行使用メモリ | 92,520 KB |
最終ジャッジ日時 | 2024-08-03 09:25:11 |
合計ジャッジ時間 | 6,863 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 131 ms
91,088 KB |
testcase_01 | AC | 151 ms
91,040 KB |
testcase_02 | AC | 132 ms
90,932 KB |
testcase_03 | AC | 130 ms
91,116 KB |
testcase_04 | AC | 147 ms
92,076 KB |
testcase_05 | AC | 302 ms
92,464 KB |
testcase_06 | AC | 210 ms
92,416 KB |
testcase_07 | AC | 196 ms
92,352 KB |
testcase_08 | AC | 195 ms
92,364 KB |
testcase_09 | AC | 177 ms
92,520 KB |
testcase_10 | AC | 133 ms
90,952 KB |
testcase_11 | AC | 152 ms
91,120 KB |
testcase_12 | AC | 133 ms
91,196 KB |
testcase_13 | AC | 130 ms
91,220 KB |
testcase_14 | AC | 127 ms
91,156 KB |
testcase_15 | AC | 131 ms
91,192 KB |
testcase_16 | AC | 138 ms
91,124 KB |
testcase_17 | AC | 136 ms
91,124 KB |
testcase_18 | AC | 133 ms
91,260 KB |
testcase_19 | AC | 153 ms
91,236 KB |
testcase_20 | AC | 131 ms
91,220 KB |
testcase_21 | AC | 136 ms
91,572 KB |
testcase_22 | AC | 129 ms
90,880 KB |
testcase_23 | AC | 144 ms
92,028 KB |
testcase_24 | AC | 131 ms
91,284 KB |
testcase_25 | AC | 136 ms
91,144 KB |
testcase_26 | AC | 134 ms
91,268 KB |
testcase_27 | AC | 151 ms
91,208 KB |
testcase_28 | AC | 131 ms
91,268 KB |
testcase_29 | AC | 136 ms
91,148 KB |
testcase_30 | AC | 134 ms
91,052 KB |
testcase_31 | AC | 131 ms
91,200 KB |
testcase_32 | AC | 132 ms
91,088 KB |
testcase_33 | AC | 132 ms
91,444 KB |
testcase_34 | AC | 128 ms
91,016 KB |
ソースコード
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()) def divisor(n) -> list: sq = n**0.5 border = int(sq) table = [] bigs = [] for small in range(1, border + 1): if n % small == 0: table.append(small) big = n // small bigs.append(big) if border == sq: # nが平方数 bigs.pop() table += reversed(bigs) return table divs = divisor(N) divs = sorted(divs) dp = defaultdict(int) for i in range(len(divs)): n = divs[i] if n == 1: continue divs_now = divisor(n) divs_now = list(reversed(sorted(divs_now))) counter = defaultdict(int) for j in range(len(divs_now)): counter[divs_now[j]] += n // divs_now[j] for k in range(j): if divs_now[k] % divs_now[j] == 0: counter[divs_now[j]] -= counter[divs_now[k]] for num in counter: if num == n: continue dp[n] += 1 / n * counter[num] * dp[num] dp[n] += 1 dp[n] *= (n) / (n - 1) print(dp[N])