1# from titan_pylib.math.big_int import BigInt
2from typing import Union, Sequence, Final
3
4
5class BigInt:
6
7 _KETA: Final[int] = 18
8 _BAI10: Final[int] = 10**_KETA
9
10 def __init__(
11 self, a: Union[Sequence[int], int, str], _internal: bool = False
12 ) -> None:
13 if _internal:
14 self.a = a
15 self.n = len(a)
16 return
17 self.sgn = True
18 if isinstance(a, int):
19 a = str(a)
20 if a and a[0] == "-":
21 self.sgn = False
22 start = 1 if a and (a[0] == "-" or a[0] == "+") else 0
23 arr = []
24 for i in range(len(a) - 1, start - 1, -self._KETA):
25 val = 0
26 for j in range(max(start, i - self._KETA + 1), i + 1):
27 val *= 10
28 val += int(a[j])
29 arr.append(val)
30 self.a = arr
31 self.n = len(self.a)
32
33 @classmethod
34 def _gen(cls, a: list[int], sgn: bool):
35 res = cls(a, True)
36 res.sgn = sgn
37 if res.n == 0:
38 res.sgn = True
39 return res
40
41 def __eq__(self, other: "BigInt") -> bool:
42 return self.sgn == other.sgn and self.a == other.a
43
44 def __ge__(self, other: "BigInt") -> bool:
45 return self == other or other < self
46
47 def __gt__(self, other: "BigInt") -> bool:
48 return other < self
49
50 def __le__(self, other: "BigInt") -> bool:
51 return self == other or self < other
52
53 def __lt__(self, other: "BigInt") -> bool:
54 if self.sgn and (not other.sgn):
55 return False
56 if (not self.sgn) and other.sgn:
57 return True
58 if self.sgn:
59 # both +
60 if self.n == other.n:
61 for i in range(self.n - 1, -1, -1):
62 if self.a[i] < other.a[i]:
63 return True
64 if self.a[i] > other.a[i]:
65 return False
66 return False # same
67 return self.n < other.n
68 else:
69 # both -
70 if self.n == other.n:
71 for i in range(self.n - 1, -1, -1):
72 if self.a[i] > other.a[i]:
73 return True
74 if self.a[i] < other.a[i]:
75 return False
76 return False # same
77 return self.n > other.n
78
79 def _abs_lt(self, other: "BigInt") -> bool:
80 if self.n == other.n:
81 for i in range(self.n - 1, -1, -1):
82 if self.a[i] == other.a[i]:
83 continue
84 return self.a[i] < other.a[i]
85 return False # same
86 return self.n < other.n
87
88 @classmethod
89 def _add(cls, b1: "BigInt", b2: "BigInt") -> list[int]:
90 if b1.n < b2.n:
91 b1, b2 = b2, b1
92 a = []
93 carry = 0
94 for i in range(b1.n):
95 x = b1.a[i] + carry
96 if i < b2.n:
97 x += b2.a[i]
98 if x >= cls._BAI10:
99 carry = 1
100 x -= cls._BAI10
101 else:
102 carry = 0
103 a.append(x)
104 if carry:
105 a.append(carry)
106 return a
107
108 @classmethod
109 def _sub(cls, b1: "BigInt", b2: "BigInt") -> tuple[list[int], bool]:
110 sgn = True
111 if b1._abs_lt(b2):
112 b1, b2 = b2, b1
113 sgn = False
114 a = []
115 kurisagari = False
116 for i in range(b1.n):
117 val = b1.a[i] - kurisagari
118 if i < b2.n:
119 val -= b2.a[i]
120 if val < 0:
121 kurisagari = True
122 val += cls._BAI10
123 else:
124 kurisagari = False
125 a.append(val)
126 while len(a) > 1 and a[-1] == 0:
127 a.pop()
128 return a, sgn
129
130 def __add__(self, other: "BigInt") -> "BigInt":
131 sgn = True
132 if self.sgn and other.sgn:
133 a = self._add(self, other)
134 sgn = True
135 elif (not self.sgn) and (not other.sgn):
136 a = self._add(self, other)
137 sgn = False
138 else:
139 if self.sgn:
140 a, sgn = self._sub(self, other)
141 else:
142 a, sgn = self._sub(other, self)
143 return self._gen(a, sgn)
144
145 def __sub__(self, other: "BigInt") -> "BigInt":
146 other.sgn = not other.sgn
147 res = self + other
148 other.sgn = not other.sgn
149 return res
150
151 __iadd__ = __add__
152 __isub__ = __sub__
153
154 def __mul__(self, other: "BigInt") -> "BigInt":
155 raise NotImplementedError
156
157 def __int__(self) -> int:
158 res = 0
159 for i in range(self.n - 1, -1, -1):
160 res *= self._BAI10
161 res += self.a[i]
162 if not self.sgn:
163 res = -res
164 return res
165
166 def __neg__(self) -> "BigInt":
167 return self._gen(self.a[:], not self.sgn)
168
169 def __abs__(self) -> "BigInt":
170 return self._gen(self.a[:], True)
171
172 def __str__(self):
173 return ("" if self.sgn else "-") + "".join(
174 map(
175 lambda x: str(x[1]).zfill(0 if x[0] == 0 else self._KETA),
176 enumerate(reversed(self.a)),
177 )
178 )
179
180 __repr__ = __str__