### NichkeCoder's blog

By NichkeCoder, history, 7 weeks ago,

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.

• -2

 » 7 weeks ago, # | ← Rev. 4 →   +4 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#include #include #include #include #include using namespace std; typedef long long LL; const LL MOD = 1e9+7; LL mod_pow(LL base, LL exp) { if(exp==0) return 1; if(exp&1) return (base*mod_pow(base,exp-1))%MOD; else return mod_pow((base*base)%MOD, exp>>1); } LL solve(int n, LL x, vector& a) { map ctr; LL sum = 0; for(const LL& v : a) { ctr[v]++; sum += v; } stack> candidates; for(const auto& p : ctr) candidates.push({sum-p.first,p.second}); while(!candidates.empty()) { auto[v,ct] = candidates.top(); candidates.pop(); if(ct%x==0) { if(!candidates.empty() && candidates.top().first==v+1) candidates.top().second += ct/x; else candidates.push({v+1,ct/x}); } else return min(v,sum); } assert(false); return -1; } int main() { LL n, x; cin >> n >> x; vector a(n); for(int i = 0; i < n; i++) cin >> a[i]; cout<
•  » » 7 weeks ago, # ^ |   +8 Thank you so much for the explanation. The first half truly helped me understand the whole idea. Thanks again!
 » 7 weeks ago, # |   0 Auto comment: topic has been updated by NichkeCoder (previous revision, new revision, compare).