#1058840 (PyPy3) No.2829 GCD Divination

• 問題: No.2829 GCD Divination
• ユーザー: 已经死了
• 提出日時: 2025-03-24 00:12:55
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 1,109 ms / 2,000 ms
• コード長: 5,431 bytes
• コンパイル時間: 383 ms
• コンパイル使用メモリ: 82,548 KB
• 実行使用メモリ: 418,624 KB
• 最終ジャッジ日時: 2025-03-24 00:13:17
• 合計ジャッジ時間: 19,675 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
other	AC * 35

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
import os,sys,random,threading
#sys.exit() 退出程序
#sys.setrecursionlimit(10**6) #调整栈空间
from random import randint,choice,shuffle
#randint(a,b)从[a,b]范围随机选择一个数
#choice(seq)seq可以是一个列表,元组或字符串,从seq中随机选取一个元素
#shuffle(x)将一个可变的序列x中的元素打乱
from copy import deepcopy
from io import BytesIO,IOBase
from types import GeneratorType
from functools import lru_cache,reduce
#reduce(op,迭代对象)
from bisect import bisect_left,bisect_right
#bisect_left(x) 大于等于x的第一个下标
#bisect_right(x) 大于x的第一个下标
from collections import Counter,defaultdict,deque
from itertools import accumulate,combinations,permutations
#accumulate(a)用a序列生成一个累积迭代器，一般list化前面放个[0]做前缀和用
#combinations(a,k)a序列选k个 组合迭代器
#permutations(a,k)a序列选k个 排列迭代器
from heapq import  heapify,heappop,heappush
#heapify将列表转为堆
from typing import Generic,Iterable,Iterator,TypeVar,Union,List
from string import ascii_lowercase,ascii_uppercase,digits
#小写字母，大写字母，十进制数字
from math import ceil,floor,sqrt,pi,factorial,gcd,log,log10,log2,inf
#ceil向上取整，floor向下取整 ，sqrt开方 ，factorial阶乘
from decimal import Decimal,getcontext
#Decimal(s) 实例化Decimal对象,一般使用字符串
#getcontext().prec=100 修改精度
from sys import stdin, stdout, setrecursionlimit
input = lambda: sys.stdin.readline().rstrip("\r\n")
MI = lambda :map(int,input().split())
li = lambda :list(MI())
ii = lambda :int(input())
mod = int(1e9 + 7) #998244353
inf = 1<<60
py = lambda :print("YES")
pn = lambda :print("NO")
DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右下左上
DIRS8 = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0),(-1, 1)]  # →↘↓↙←↖↑↗
class PrimeTable:
    def __init__(self, n=int((10**9)**0.5)+3) -> None:
        #值域1e9的话考虑质因子，只需小于等于(10**9)**0.5的质数即可
        #任意一个正整数n最多只有一个质因子大于根号n
        self.n = n
        self.primes = [] #小于等于n的所有质数
        self.min_div = [0] * (n+1)
        self.min_div[1] = 1
 
        mu = [0] * (n+1)
        phi = [0] * (n+1)
        mu[1] = 1
        phi[1] = 1
        self.mu=mu
 
        for i in range(2, n+1):
            if not self.min_div[i]:
                self.primes.append(i)
                self.min_div[i] = i
                mu[i] = -1
                phi[i] = i-1
            for p in self.primes:
                if i * p > n: break
                self.min_div[i*p] = p
                if i % p == 0:
                    phi[i*p] = phi[i] * p
                    break
                else:
                    mu[i*p] = -mu[i]
                    phi[i*p] = phi[i] * (p - 1)
    # x是否质数
    def is_prime(self, x:int):
        if x < 2: return False
        if x <= self.n: return self.min_div[x] == x
        for p in self.primes:
            if p * p > x: break
            if x % p == 0: return False
        return True
    # x分解质因数:[p, cnt] 质因子p，个数cnt
    # 用的yield，当作一个可遍历的数据对象
    #一个数一定可以分解为多个质数的连乘积
    #n = x^a * y^b * z^c ...  （x,y,z为质因数） n的约数个数=(a+1)(b+1)...(y+1)
    def prime_factorization(self, x:int):
        for p in self.primes:
            if p * p > x: break
            if x <= self.n: break
            if x % p == 0:
                cnt = 0
                while x % p == 0: cnt += 1; x //= p
                yield p, cnt
        while (1 < x and x <= self.n):
            p, cnt = self.min_div[x], 0
            while x % p == 0: cnt += 1; x //= p
            yield p, cnt
        if x >= self.n and x > 1:
            #小于等于(10**9)**0.5的质数除干净了，如果还大于1
            # 那么余下的数一定是一个大于等于n的质数
            yield x, 1
            
    # x的所有因数
    def get_factors(self, x:int):
        factors = [1]
        for p, b in self.prime_factorization(x):
            n = len(factors)
            for j in range(1, b+1):
                for d in factors[:n]:
                    factors.append(d * (p ** j))
        return factors
def isprime(n):    #试除法，判断一个数是否为质数
    if n<2:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True
def tag_primes_eratosthenes(n):  
    # 埃氏筛,筛出[0,n)区间内的所有质数   
    # 第1e5个数字是1299709
    # 1e5前有9592个质数
    primes = [ True ]*n
    primes[ 0 ] = primes[ 1 ] = False  # 0和1不是质数
    for i in range(2,int(n**0.5)+1):
        if primes[i]:
            primes[i * i::i] = [ False ] * ((n - 1 - i * i) // i + 1)
    return primes
n=ii()
pt = PrimeTable(n+1)
dp=[0]*(n+1)  
def cal(x):
    fac=sorted(pt.get_factors(x))
    m=len(fac)
    cnt=[0]*m
    for i in range(m-1,-1,-1):
        cnt[i]=x//fac[i]
        for j in range(i+1,m):
            if fac[j]%fac[i]==0:
                cnt[i]-=cnt[j]
    ans=0
    for j in range(m-1):
        ans+=cnt[j]*dp[fac[j]]
    ans=ans/x+1
    #print(x,cnt,fac,dp,ans,1-1/x)
    dp[x]=ans/(1-1/x)
for i in sorted(pt.get_factors(n)):
    if i==1:
        continue
    cal(i)
print(dp[-1])
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX