When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

VeryGoodVeryGood's blog

By VeryGoodVeryGood, history, 4 years ago, In English

Hi CodeForces, I've been trying to solve this problem for a long time now but really don't get anything about it. I have read the editorial but I can't seem to understand what author means by saying cnt is multiple of x. How does that help solving the problem, could somebody provide an example of how it works or a better explanation. Thanks and sorry if this question is a bit dumb.

EDIT: I am very sorry for posting duplicate question (I have found a comment already discussing this problem) and not specifying the details. Will search next time.

  • Vote: I like it
  • -2
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 4   Vote: I like it +4 Vote: I do not like it

Let $$$sum=a_1+a_2+\dots+a_n$$$. Since $$$t=x^{sum}$$$, we know the GCD of $$$s$$$ and $$$t$$$ is some power of $$$x$$$. So, let's try to find the largest $$$v$$$ such that $$$x^v$$$ divides $$$s$$$.

Assume that $$$s$$$ is written in base $$$x$$$ notation, that is to say $$$s = d_k x^k + d_{k-1} x^{k-1} + \dots + d_2 x^2 + d_1 x^1 + d_0 x^0$$$ where $$$0 \leq d_i < x$$$. Phrased in this way, it should be evident that the largest $$$v$$$ such that $$$x^v$$$ divides $$$s$$$ is the smallest $$$v$$$ such that $$$d_v > 0$$$. Why? Because then it would be written as $$$s = d_k x^k + \dots + d_v x^v$$$.

Let's try to write $$$s$$$ in base $$$x$$$ then. Let $$$s_i$$$ be the numerator of the $$$i$$$ th term, which should be $$$\prod_{j \neq i} x^{a_j}$$$ (because we just multiply all other denominators). This is the same as $$$x^{\sum_{j \neq i} a_j}$$$, which itself is just $$$x^{sum - a_i}$$$.

Since $$$s$$$ is the sum of all these numerators, we have that $$$s = \sum_i x^{sum-a_i}$$$. However, note that the $$$a_i$$$ are also not necessarily distinct. Let $$$ct[k]$$$ be the number of times that the term $$$x^k$$$ exists in that sum. Then, we have $$$s = \sum_k ct[k] x^k$$$.

For example, suppose $$$a = [1,1,1,1,2,3,3]$$$. Then, $$$sum = 12$$$ and we have terms with degree $$$11$$$, $$$10$$$, and $$$9$$$, with $$$ct[11] = 4$$$, $$$ct[10]=1$$$, and $$$ct[9]=2$$$. So $$$s = 4x^{11} + 1x^{10} + 2x^9$$$.

Are we done? If $$$s = \sum_k ct[k] x^k$$$ is already written in base $$$x$$$ notation, then all we have to do is find the smallest $$$k$$$ such that $$$ct[k]$$$ is nonzero. Unfortunately, we are not quite done! Notice that in base $$$x$$$ notation, the coefficients must respect $$$0 \leq d_i < x$$$, but that is not necessarily the case for $$$ct[k]$$$.

In particular, consider when $$$ct[k]$$$ is divisible by $$$x$$$. This is the case in the first sample input, where $$$s = 2 \times 2^2$$$. Note that in real base $$$x$$$ notation, this actually ends up being $$$s = 1 \times 2^3$$$, so $$$v=3$$$, not $$$2$$$.

So, we are going to perform "carrying". We will force each coefficient to be from $$$0$$$ to $$$x-1$$$, then "carry" the remaining to the next column. If this place value is still non-zero after all the addition and carrying, then we are done. Otherwise, we have to move on to the next place value, and so on.

Consider the smallest value of $$$k$$$ in our summation. Let $$$q = \left\lfloor\frac{ct[k]}{x}\right\rfloor$$$ and $$$r = ct[k] \bmod x$$$, then we can write $$$ct[k] = xq+r$$$. Then, $$$ct[k]x^k = qx^{k+1} + rx^k$$$. If $$$r \neq 0$$$ (i.e. if $$$ct[k]$$$ is not divisible by $$$x$$$), then we know $$$v=k$$$ already, because then $$$rx^k$$$ would be the smallest non zero digit in base $$$x$$$. However, if $$$r=0$$$, then unfortunately we have to continue our search. Perform ct[k+1] += q because the coefficient of $$$x^{k+1}$$$ gets increased by $$$q$$$. Then, continue our search until we do find a coefficient that is not divisible by $$$x$$$.

The editorial (and my solution) suggests that you do this with a stack. Push the coefficients of each $$$x^k$$$ (which is initially just $$$ct[k]$$$) into a stack, such that the coefficient of the largest degree $$$k$$$ is at the bottom of the stack, and the coefficient of the smallest degree $$$k$$$ is at the top of the stack.

Inspect the top element of the stack. If it is not divisible by $$$x$$$, return $$$k$$$ because we are done. If it is divisible by $$$x$$$, then we need to update the coefficient of $$$k+1$$$ by adding $$$q$$$ to it (because of the "carrying"). If $$$x^{k+1}$$$ exists in our stack, it should be the next element. If it is not in our stack, then just push $$$q$$$ on because it should come next.

Keep popping and inspecting elements from the stack until you are done.

This tells us $$$v$$$, the largest power of $$$x$$$ which divides $$$s$$$. Thus, the GCD of $$$s$$$ and $$$t$$$ is $$$\min(v,sum)$$$.

If you need it, here is my implementation in C++17.

Code
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thank you so much for the explanation. The first half truly helped me understand the whole idea. Thanks again!