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