1# from titan_pylib.math.pollard_rho import PollardRho
2# from titan_pylib.math.is_prime64 import is_prime64
3def is_prime64(n: int) -> bool:
4 # assert 1 <= n and n <= 1<<64 # = 18446744073709551616
5 if n == 1:
6 return False
7 if n == 2:
8 return True
9 if not n & 1:
10 return False
11 p = (
12 (2, 7, 61)
13 if n < 1 << 30
14 else (2, 325, 9375, 28178, 450775, 9780504, 1795265022)
15 )
16 d = n - 1
17 d >>= (d & -d).bit_length() - 1
18 for a in p:
19 if n <= a:
20 break
21 t = d
22 y = pow(a, t, n)
23 while t != n - 1 and y != 1 and y != n - 1:
24 y = y * y % n
25 t <<= 1
26 if y != n - 1 and not t & 1:
27 return False
28 return True
29from collections import Counter
30from math import gcd
31from random import Random
32
33
34class PollardRho:
35
36 # 高速素因数分解
37 # 124376107291
38
39 _rand = Random(None)
40 _L = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
41 _P200 = [
42 2,
43 3,
44 5,
45 7,
46 11,
47 13,
48 17,
49 19,
50 23,
51 29,
52 31,
53 37,
54 41,
55 43,
56 47,
57 53,
58 59,
59 61,
60 67,
61 71,
62 73,
63 79,
64 83,
65 89,
66 97,
67 101,
68 103,
69 107,
70 109,
71 113,
72 127,
73 131,
74 137,
75 139,
76 149,
77 151,
78 157,
79 163,
80 167,
81 173,
82 179,
83 181,
84 191,
85 193,
86 197,
87 199,
88 ]
89
90 @classmethod
91 def factorization(cls, n: int) -> Counter:
92 res = Counter()
93 for p in cls._P200:
94 if n % p == 0:
95 cnt = 0
96 while n % p == 0:
97 cnt += 1
98 n //= p
99 res[p] = cnt
100 if n == 1:
101 return res
102 while n > 1:
103 f = cls._pollard_rho(n)
104 cnt = 0
105 while n % f == 0:
106 cnt += 1
107 n //= f
108 res[f] += cnt
109 return res
110
111 @classmethod
112 def _pollard_rho(cls, n: int) -> int:
113 if is_prime64(n):
114 return n
115 while True:
116 x = cls._rand.randrange(n)
117 c = cls._rand.randrange(n)
118 y = (x * x + c) % n
119 d = 1
120 while d == 1:
121 d = gcd(x - y, n)
122 x = (x * x + c) % n
123 y = (y * y + c) % n
124 y = (y * y + c) % n
125 if 1 < d < n:
126 return cls._pollard_rho(d)