1# 展開に失敗しました
2from collections import Counter
3
4
5class Osa_k:
6 """高速素因数分解
7 init: O(NloglogN)
8 N個の数の素因数分解 : O(NlogA)
9 """
10
11 def __init__(self, n: int) -> None:
12 _min_factor = list(range(n + 1))
13 for i in range(2, int(n**0.5) + 1):
14 if _min_factor[i] == i:
15 for j in range(2, int(n // i) + 1):
16 if _min_factor[i * j] > i:
17 _min_factor[i * j] = i
18 self._min_factor = _min_factor
19
20 def p_factorization(self, n: int) -> list[int]:
21 ret = []
22 _min_factor = self._min_factor
23 while n > 1:
24 ret.append(_min_factor[n])
25 n //= _min_factor[n]
26 return ret
27
28 def p_factorization_Counter(self, n: int) -> Counter:
29 ret = Counter()
30 _min_factor = self._min_factor
31 while n > 1:
32 ret[_min_factor[n]] += 1
33 n //= _min_factor[n]
34 return ret
35
36 def get_divisors(self, n: int) -> set:
37 def dfs(indx, val):
38 nonlocal f, m, ret
39 k, v = f[indx]
40 if indx + 1 < m:
41 for i in range(v + 1):
42 dfs(indx + 1, val * k**i)
43 else:
44 for i in range(v + 1):
45 ret.add(val * k**i)
46
47 f = list(self.p_factorization_Counter(n).items())
48 m = len(f)
49 ret = set()
50 dfs(0, 1)
51 return ret
52
53
54def get_divisors(n: int) -> list[int]:
55 """約数全列挙. / O(√N)"""
56 l = []
57 r = []
58 for i in range(1, int(n**0.5) + 1):
59 if n % i == 0:
60 l.append(i)
61 if i != n // i:
62 r.append(n // i)
63 return l + r[::-1]
64
65
66def factorization(n: int) -> list[tuple[int, int]]:
67 "Nを1回素因数分解する / O(√N)"
68 ret = []
69 if n == 1:
70 return ret
71 for i in range(2, int(-(-(n**0.5) // 1)) + 1):
72 if n == 1:
73 break
74 if n % i == 0:
75 cnt = 0
76 while n % i == 0:
77 cnt += 1
78 n //= i
79 ret.append((i, cnt))
80 if n != 1:
81 ret.append((n, 1))
82 return ret
83
84
85def factorization_counter(n: int) -> Counter:
86 "Nを1回素因数分解する / O(√N)"
87 ret = Counter()
88 if n == 1:
89 return ret
90 for i in range(2, int(-(-(n**0.5) // 1)) + 1):
91 if n == 1:
92 break
93 if n % i == 0:
94 cnt = 0
95 while n % i == 0:
96 cnt += 1
97 n //= i
98 ret[i] = cnt
99 if n != 1:
100 ret[n] = 1
101 return ret
102
103
104def divisors_num(n: int) -> int:
105 "Nの約数の個数を求める / O(√N)"
106 cnt = 0
107 for i in range(1, int(n**0.5) + 1):
108 if n % i == 0:
109 cnt += 1
110 if i != n // i:
111 cnt += 1
112 return cnt
113
114
115def divisors_num_all(n) -> list[int]:
116 "N以下のそれぞれの数の約数の個数を求める / O(NlogN)"
117 li = [0] * (n + 1)
118 for i in range(1, n + 1):
119 for j in range(i, n + 1, i):
120 li[j] += 1
121 return li
122
123
124def primefactor_num(n) -> list[int]:
125 "N以下のそれぞれの数の素因数の種類数を求める / O(NloglogN)"
126 cnt = [0] * (n + 1)
127 for i in range(2, n + 1):
128 if cnt[i] >= 1:
129 continue
130 for j in range(i, n + 1, i):
131 cnt[j] += 1
132 return cnt
133
134
135def get_primelist(limit: int) -> list[int]:
136 "エラトステネスの篩(N以下の素数を返す) / O(NloglogN)"
137 p = [1] * (limit + 1)
138 p[0] = 0
139 p[1] = 0
140 for i in range(2, int(limit**0.5) + 1):
141 if not p[i]:
142 continue
143 for j in range(i + i, limit + 1, i):
144 p[j] = 0
145 return [i for i, x in enumerate(p) if x]
146
147
148def get_prime_count(limit: int) -> int:
149 "N以下の素数の個数を求める / O(NloglogN)"
150 ret = 0
151 for i in range(2, limit):
152 for j in range(2, int(limit**0.5) + 1):
153 if i % j == 0:
154 break
155 else:
156 ret += 1
157 return ret
158
159
160def factorization_eratos(n: int, primes: list[int]) -> list[int]:
161 "事前にエラトステネスとかでsart(N)以下の素数を全列挙しておく"
162 "O(sqrt(N)log(log(sqrt(N)) + log(N))"
163 res = []
164 for p in primes:
165 # if is_prime64(n): break
166 if p * p > n:
167 break
168 if n % p == 0:
169 n //= p
170 while n % p == 0:
171 n //= p
172 res.append(p)
173 if n != 1:
174 res.append(n)
175 return res