Big integers with negative digits

Правка en4, от adamant, 2023-04-30 01:44:45

Hi everyone!

Today we will talk about something that might be useful in programming competitions. Yay! Also great thanks to antontrygubO_o for sharing this with me and others in a Discord server.

Let's implement a data structure that maintains a big number $$$N$$$ in base $$$b$$$ and supports the following:

  • Given integers $$$|x|, |y| \leq n$$$, add $$$x b^y$$$ to $$$N$$$.
  • Given $$$k$$$ and assuming $$$N \geq 0$$$, print the $$$k$$$-th digit of $$$N$$$.
  • Check if $$$N$$$ is positive, negative or equals to $$$0$$$.

Each operation should take at most $$$O(\log n)$$$ amortized time and $$$O(q)$$$ memory. While some approach you may think of immediately would imply using segment tree, or a similar structure, the solution proposed here only requires std::map, so it's much shorter and easier to implement (at the slight expense of increased constant factor). It may be used in the following problems:

If you implement the big integers in these numbers the standard way (i.e. keeping digits in the $$$[0, b)$$$ segment, carefully executing carries, etc), you will quickly learn that you may get in trouble because you may be forced to do and undo a lot of carry operations which chain up and so you need to frequently change large segments between the values of $$$0$$$ and $$$b-1$$$.

Now, stop being fooled by the non-negative propaganda! You don't have to do it! Let's give ourselves some slack and allow negative digits. Well, just a bit of them. Instead of maintaining digits in $$$[0,b)$$$, let's now maintain them in the interval $$$(-b, b)$$$. It seems like a tiny change, but the effect is tremendous. On one hand, the representation of any number is not unique anymore. On the other hand, when we actually reach the value $$$b$$$ or $$$-b$$$, we wrap them back to $$$0$$$, and carry $$$1$$$ or $$$-1$$$ to the next digit correspondingly.

Noticed anything? The carry now wraps us from the endpoints of the interval to its middle instead of from one endpoint to another! It would be easy to add $$$1$$$ to a particular bit, turn it into $$$b$$$ and cause a chain of carries by it. But! If after that we add $$$-1$$$ to the same bit, it will not wrap all the bits back to $$$b-1$$$! It will just change this specific bit to $$$-1$$$! So, we give up the uniqueness of the representation, but we gain a whole lot of stability in exchange.

The C++ implementation for the first two queries is also quite concise:

code

I tested it on #2302. 「NOI2017」整数 and it works!

P.S. Applying it to 1817E - Half-sum and 1810F - M-tree is left to the curious reader as an exercise :)

P.P.S. Is this trick well-known? Does it have a name?

Теги bignum

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский adamant 2023-04-30 11:12:57 20 Tiny change: '\n- Given integers ' -> '\n- Given (possibly negative) integers '
en7 Английский adamant 2023-04-30 09:19:30 4
en6 Английский adamant 2023-04-30 01:48:06 2
en5 Английский adamant 2023-04-30 01:47:22 16
en4 Английский adamant 2023-04-30 01:44:45 8 Tiny change: 'p\nstruct nega_num {\n ' -> 'p\nstruct trygub_num {\n '
en3 Английский adamant 2023-04-30 01:40:57 18 Tiny change: 'q)$ memory, where $q$ is the number of queries. While so' -> 'q)$ memory. While so'
en2 Английский adamant 2023-04-30 01:39:46 43
en1 Английский adamant 2023-04-30 01:36:37 3517 Initial revision (published)