codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2241.md (27914B)


      1 Source: https://codeforces.com/blog/entry/154698
      2 
      3 Thanks for participating. I apologize for the unexpectedly hard B. Apart from that, I hope you liked the problems and enjoyed the round!
      4 
      5 I would like to thank [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED"), [Forge](/profile/Forge "Мастер Forge"), and [awesomeguy856](/profile/awesomeguy856 "Гроссмейстер awesomeguy856") for pointing out an elegant $\mathcal{O}(n)$ solution for problem G.
      6 
      7 I would also like to thank [temporary1](/profile/temporary1 "Мастер temporary1") for helping me write the editorial for problem F and [Forge](/profile/Forge "Мастер Forge") and [reirugan](/profile/reirugan "Кандидат в мастера reirugan") for proofreading the editorial.
      8 
      9 **Rating predictions**
     10 
     11 | Predictor | A | B | C | D | E | F | G |
     12 | --- | --- | --- | --- | --- | --- | --- | --- |
     13 | [wakanda-forever](/profile/wakanda-forever "Кандидат в мастера wakanda-forever") | $800$ | $1000$ | $1000$ | $1200$ | $1500$ | $1800$ | $2100$ |
     14 | [expertaq](/profile/expertaq "Эксперт expertaq") | $800$ | $1000$ | $1100$ | $1200$ | $1600$ | $1700$ | $2000$ |
     15 | [reirugan](/profile/reirugan "Кандидат в мастера reirugan") | $800$ | $900$ | $1000$ | $1200$ | $1500$ | $1700$ | $1900$ |
     16 | [yse](/profile/yse "Кандидат в мастера yse") | $800$ | $800$ | $800$ | $1100$ | $1500$ | $1700$ | $1900$ |
     17 | [Argentum47](/profile/Argentum47 "Кандидат в мастера Argentum47") | $800$ | $900$ | $1000$ | $1200$ | $1700$ | $1700$ | $2100$ |
     18 | [simplelife](/profile/simplelife "Эксперт simplelife") | $800$ | $800$ | $900$ | $1100$ | $1500$ | $1900$ | $2200$ |
     19 | [omsincoconut](/profile/omsincoconut "Мастер omsincoconut") | $800$ | $1200$ | $1100$ | $1300$ | $1800$ | $1900$ | $2300$ |
     20 | [kevinxiehk](/profile/kevinxiehk "Гроссмейстер kevinxiehk") | $800$ | $1000$ | $1000$ | $1200$ | $1700$ | $1900$ | $2200$ |
     21 | [Edeeva](/profile/Edeeva "Кандидат в мастера Edeeva") | $800$ | $1000$ | $1000$ | $1300$ | $1600$ | $1800$ | $2200$ |
     22 | [Forge](/profile/Forge "Мастер Forge") | $800$ | $1000$ | $1100$ | $1400$ | $1700$ | $1900$ | $2100$ |
     23 | [_istil](/profile/_istil "Гроссмейстер _istil") | $800$ | $900$ | $1100$ | $1200$ | $1600$ | $1800$ | $2100$ |
     24 | [Jrke](/profile/Jrke "Мастер Jrke") | $800$ | $900$ | $1100$ | $1400$ | $1700$ | $1800$ | $2100$ |
     25 | [temporary1](/profile/temporary1 "Мастер temporary1") | $800$ | $900$ | $1000$ | $1400$ | $1600$ | $1800$ | $2000$ |
     26 | [skellyboi05](/profile/skellyboi05 "Эксперт skellyboi05") | $800$ | $900$ | $1000$ | $1300$ | $1600$ | $1700$ | ----- |
     27 | [nik_exists](/profile/nik_exists "Эксперт nik_exists") | $800$ | $1000$ | $900$ | $1200$ | $1600$ | $1700$ | ----- |
     28 | [Proof_by_QED](/profile/Proof_by_QED "Мастер Proof_by_QED") | $800$ | $900$ | $900$ | $1100$ | $1700$ | $1500$ | $1900$ |
     29 | [Lilypad](/profile/Lilypad "Кандидат в мастера Lilypad") | $800$ | $900$ | $1200$ | $1200$ | $1700$ | $1900$ | $2100$ |
     30 
     31 #### [2241A - Дели и властвуй](/contest/2241/problem/A "Codeforces Round 1107 (Div. 3)")
     32 
     33 **Idea**
     34 
     35 The operation allows us to choose a divisor $z$ of $x$ and update $x := \frac{x}{z}$.
     36 
     37 Since $z$ is a divisor of $x$, the resulting value $\frac{x}{z}$ is strictly an integer and is **also a divisor** of $x$. Because we can freely choose *any* valid $z$, a single operation effectively allows us to replace $x$ with any of its divisors.
     38 
     39 Applying this operation multiple times does not yield any additional numbers, because a divisor of a divisor is still just a divisor of the original $x$. Therefore, the set of all possible numbers reachable from $x$ is strictly limited to its divisors.
     40 
     41 Therefore, to solve the problem:
     42 
     43 * If $y$ is a divisor of $x$ (i.e., $x \bmod y = 0$), we output `YES`. We can reach $y$ in at most $1$ operation by choosing $z = \frac{x}{y}$.
     44 * If $y$ is not a divisor of $x$, we output `NO`, as it is impossible to reach.
     45 
     46 Time Complexity: $\mathcal{O}(1)$.
     47 
     48 **Implementation**
     49 
     50 ```
     51 #include<bits/stdc++.h>
     52 using namespace std;
     53  
     54 int main(){
     55  
     56     int tt;
     57     cin >> tt;
     58  
     59     while(tt--){
     60         int x, y;
     61         cin >> x >> y;
     62         
     63         cout << (x % y == 0 ? "YES" : "NO") << '\n';
     64     }
     65  
     66     return 0;
     67 }
     68 ```
     69 
     70 **Rate The Problem!**
     71 
     72 * Best Problem
     73 * Good Problem
     74 * Okay Problem
     75 * Bad Problem
     76 * Didn't Solve
     77 
     78 #### [2241B - Приумножь хорошее](/contest/2241/problem/B "Codeforces Round 1107 (Div. 3)")
     79 
     80 **Idea**
     81 
     82 Let $d$ be the number of digits of $x$, and choose $y = 10^d + 1$. The number $y$ contains only the digits $0$ and $1$, so $y$ is good. Also,
     83 
     84 $ x \cdot y = x \cdot (10^d+1) = x \cdot 10^d + x. $
     85 
     86 Since $x \lt 10^d$, multiplying by $10^d$ simply shifts $x$ by $d$ positions. Therefore, $x \cdot y$ is exactly the decimal concatenation of $x$ with itself. Hence, the set of digits appearing in $x \cdot y$ is the same as in $x$. Since $x$ is good, $x \cdot y$ is good as well.
     87 
     88 Thus, for every test case, one of the possible answers is simply
     89 
     90 $ y = 10^d + 1. $
     91 
     92 The construction always satisfies $2 \le y \le 10^9$.
     93 
     94 Time Complexity: $\mathcal{O}(\log_{10}(x))$.
     95 
     96 **Implementation**
     97 
     98 ```
     99 #include<bits/stdc++.h>
    100 using namespace std;
    101  
    102 int main(){
    103  
    104     int tt;
    105     cin >> tt;
    106  
    107     while(tt--){
    108         int x;
    109         cin >> x;
    110  
    111         int y = 1;
    112  
    113         while(x > 0){
    114             y *= 10;
    115             x /= 10;
    116         }
    117  
    118         cout << y + 1 << '\n';
    119     }
    120  
    121     return 0;
    122 }
    123 ```
    124 
    125 **Rate The Problem!**
    126 
    127 * Best Problem
    128 * Good Problem
    129 * Okay Problem
    130 * Bad Problem
    131 * Didn't Solve
    132 
    133 #### [2241C - УдалиладУ](/contest/2241/problem/C "Codeforces Round 1107 (Div. 3)")
    134 
    135 **Idea**
    136 
    137 Let $c$ be the number of positions $i$ such that $s_i \ne s_{i+1}$.
    138 
    139 If $c=0$, all characters are equal. The whole string is always a palindrome, so we can repeatedly delete characters until only one remains.
    140 
    141 If $c=1$, the string consists of exactly two contiguous blocks of equal characters. Any palindrome of length at least $2$ must be contained entirely inside one of these blocks, so every operation only shortens a block and can never remove it completely. Therefore, both blocks remain nonempty, and the minimum possible length is $2$.
    142 
    143 If $c\ge 2$, then the string has at least three blocks. First, we can shrink every block to length $1$, because any block of equal characters is itself a palindrome of length at least $2$ as long as its length is at least $2$. So we may assume the string becomes alternating.
    144 
    145 Now consider an alternating string of length at least $3$. Its last three characters are always of the form $010$ or $101$; hence, they form a palindrome. Deleting the last character of this palindrome shortens the string by $1$, and the remaining string is still alternating. Repeating this step, we can reduce the string to length $3$. Then the whole string is a palindrome, and deleting its middle character gives two equal characters, which can be reduced to length $1$ in one more move.
    146 
    147 Hence, the answer is $2$ iff $c=1$, and $1$ otherwise.
    148 
    149 Time Complexity: $\mathcal{O}(n)$.
    150 
    151 **Implementation**
    152 
    153 ```
    154 #include<bits/stdc++.h>
    155 using namespace std;
    156  
    157 int main(){
    158  
    159     int tt;
    160     cin >> tt;
    161  
    162     while(tt--){
    163         int n;
    164         string s;
    165         cin >> n >> s;
    166  
    167         int count = 0;
    168         for(int i = 0; i < n - 1; i++) if(s[i] != s[i + 1]) count++;
    169  
    170         cout << (count == 1 ? 2 : 1) << '\n';
    171     }
    172  
    173     return 0;
    174 }
    175 ```
    176 
    177 **Rate The Problem!**
    178 
    179 * Best Problem
    180 * Good Problem
    181 * Okay Problem
    182 * Bad Problem
    183 * Didn't Solve
    184 
    185 #### [2241D - Очередной способ](/contest/2241/problem/D "Codeforces Round 1107 (Div. 3)")
    186 
    187 **Idea**
    188 
    189 Let
    190 
    191 $ p_i=\sum_{j=1}^{i} a_j,\qquad q_i=\sum_{j=1}^{i} b_j. $
    192 
    193 The key is to look at prefix sums. One operation on segment $[l,r]$ adds the pattern $+1,-1,+1,-1,\dots$ starting from the left end. Therefore, the prefix sum of the modified array changes by $1$ on some prefixes and by $0$ on the others, so no prefix sum can ever decrease.
    194 
    195 Now take the special segment $[i,i+1]$. It adds $+1$ to $a_i$ and $-1$ to $a_{i+1}$, so only the $i$-th prefix sum increases by $1$, while all other prefix sums stay unchanged. Also, $[n,n]$ increases only the $n$-th prefix sum by $1$.
    196 
    197 So every prefix sum can be increased independently and never decreased. Hence, the transformation is possible iff
    198 
    199 $ p_i\le q_i \qquad \text{for all } i. $
    200 
    201 Time Complexity: $\mathcal{O}(n)$.
    202 
    203 **An Alternative Way**
    204 
    205 An alternative way to solve the problem is to first understand which operations are actually useful.
    206 
    207 Consider an operation on a subarray of length greater than $2$. Its effect is exactly the sum of the operations on consecutive subarrays of length $2$ inside it (partitioning the subarray into consecutive pairs; if its length is odd, the last element is treated as a subarray of length $1$). Therefore, every operation on a longer subarray can be decomposed into operations on length-$2$ subarrays, so it is sufficient to consider only these.
    208 
    209 Now there are only two useful operations:
    210 
    211 * applying the operation on $[i,i]$, which increases $a_i$ by $1$;
    212 * applying the operation on $[i-1,i]$, which decreases $a_i$ by $1$ and increases $a_{i-1}$ by $1$.
    213 
    214 We process the array from right to left. Suppose we are currently at position $i$.
    215 
    216 * If $a_i \lt b_i$, we simply apply the first operation $b_i-a_i$ times, increasing only $a_i$ until it becomes $b_i$.
    217 * If $a_i \gt b_i$, we apply the second operation $a_i-b_i$ times. Each application decreases $a_i$ by $1$ while increasing $a_{i-1}$ by $1$, so after these operations we have $a_i=b_i$. Any excess is pushed one position to the left.
    218 
    219 Notice that after finishing position $i$, no later operation can change it again. Hence, every position except the first can always be fixed independently. After processing all positions from $n$ down to $2$, the only remaining value is $a_1$. Since every operation can only increase $a_1$, the transformation is possible if and only if
    220 
    221 $ a_1\le b_1. $
    222 
    223 Thus, the algorithm is simply to process the array backwards as described above and finally check whether $a_1\le b_1$.
    224 
    225 Time Complexity: $\mathcal{O}(n)$.
    226 
    227 **Implementation**
    228 
    229 ```
    230 #include<bits/stdc++.h>
    231 using namespace std;
    232  
    233 int main(){
    234  
    235     int tt;
    236     cin >> tt;
    237  
    238     while(tt--){
    239         int n;
    240         cin >> n;
    241  
    242         vector<long long> a(n), b(n);
    243  
    244         for(int i = 0; i < n; i++) cin >> a[i];
    245         for(int i = 0; i < n; i++) cin >> b[i];
    246         for(int i = 1; i < n; i++) a[i] += a[i - 1];
    247         for(int i = 1; i < n; i++) b[i] += b[i - 1];
    248  
    249         bool is = 1;
    250         for(int i = 0; i < n; i++) if(a[i] > b[i]) is = 0;
    251  
    252         if(is) cout << "YES\n";
    253         else cout << "NO\n";
    254     }
    255  
    256     return 0;
    257 }
    258 ```
    259 
    260 **Rate The Problem!**
    261 
    262 * Best Problem
    263 * Good Problem
    264 * Okay Problem
    265 * Bad Problem
    266 * Didn't Solve
    267 
    268 #### [2241E - Это квадрат, честно](/contest/2241/problem/E "Codeforces Round 1107 (Div. 3)")
    269 
    270 **Idea**
    271 
    272 For any two vertices $x$ and $y$, let us denote $P(x, y)$ as the simple path from $x$ to $y$.
    273 
    274 Now, let us fix an unordered triplet of vertices ${u,v,w}$. We claim that there is exactly one vertex (say $c$) that belongs to all three paths $P(u,v)$, $P(v,w)$, and $P(w,u)$, and every other vertex is counted $0$ or $2$ times.
    275 
    276 **Proof**
    277 
    278 If one of the three vertices, say $w$, lies on the path $P(u,v)$, then clearly $w$ belongs to all three paths, because the path from $u$ to $w$ and the path from $v$ to $w$ both pass through $w$.
    279 
    280 Otherwise, $w$ does not lie on $P(u,v)$. Start from $w$ and walk towards the path $P(u,v)$. Since the graph is a tree, there is a unique first vertex $c$ where we meet $P(u,v)$. Every path from $w$ to any vertex of $P(u,v)$ must pass through $c$, so in particular both $P(w,u)$ and $P(w,v)$ pass through $c$. Also, $c \in P(u,v)$ by definition, so $c$ lies on all three paths.
    281 
    282 Now take any vertex $x$ that lies on all three paths. Since $x \in P(u,v)$ and $x \in P(w,u)$, the path from $w$ to $x$ must enter $P(u,v)$ at $x$. But the first entry point from $w$ into $P(u,v)$ is exactly $c$; hence $x=c$. So the common vertex is unique.
    283 
    284 Now take any other vertex $x\ne c$. Remove $x$ from the tree. Then the tree splits into components.
    285 
    286 If $u,v,w$ all lie in the same component, then no pairwise path uses $x$, so $x$ is counted $0$ times. If they lie in exactly two components, then exactly two of the three pairs are separated by $x$, so $x$ is counted $2$ times. If they lie in three components, then $x$ would lie on all three pairwise paths, which would make $x$ the unique common vertex, contradicting $x\ne c$.
    287 
    288 Therefore, for the product
    289 
    290 $ p(u,v)\cdot p(v,w)\cdot p(w,u), $
    291 
    292 every vertex contributes an even exponent except $c$, whose exponent is $3$. Hence, the product is a perfect square iff $a_c$ is a perfect square.
    293 
    294 So now we only need to count, for every vertex $x$ with $a_x$ a perfect square, how many triplets have $x$ as the unique common vertex. Remove $x$, and let the component sizes be $s_1,s_2,\dots,s_k$.
    295 
    296 A valid triplet is of two types:
    297 
    298 * $x$ is one of the chosen vertices. Then the other two vertices must come from two different components, so the count is
    299 
    300 $ \sum_{i \lt j} s_i s_j. $
    301 
    302 * $x$ is not chosen. Then the three chosen vertices must come from three different components, so the count is
    303 
    304 $ \sum_{i \lt j \lt \ell} s_i s_j s_\ell. $
    305 
    306 Both values can be computed in one scan over the components:
    307 
    308 $ \text{sum}=0,\quad \text{pairs}=0,\quad \text{triples}=0 $
    309 
    310 and for each component size $s$:
    311 
    312 $ \text{triples} \;\mathrel{+}= \; s\cdot \text{pairs},\qquad \text{pairs} \;\mathrel{+}= \; s\cdot \text{sum},\qquad \text{sum} \;\mathrel{+}= \; s. $
    313 
    314 Then the contribution of $x$ is $\text{pairs}+\text{triples}$.
    315 
    316 To get the component sizes for every $x$, root the tree once and store subtree sizes. For a vertex $x$, its components after deletion are all child subtrees of $x$, plus the parent-side component of size $n-\mathrm{sz}[x]$ if it exists.
    317 
    318 So the solution is:
    319 
    320 * root the tree and compute subtree sizes;
    321 * for every vertex $x$, build the sizes of components of $T-x$;
    322 * if $a_x$ is a perfect square, add $\text{pairs}+\text{triples}$ to the answer.
    323 
    324 Time Complexity: $\mathcal{O}(n)$.
    325 
    326 **Implementation**
    327 
    328 ```
    329 #include<bits/stdc++.h>
    330 using namespace std;
    331  
    332 #define ll long long
    333  
    334 int main(){
    335  
    336     int tt = 1;
    337     cin >> tt;
    338  
    339     while(tt--){
    340         ll n;
    341         cin >> n;
    342  
    343         vector<ll> a(n);
    344         for(ll i = 0; i < n; i++) cin >> a[i];
    345  
    346         vector<vector<ll>> v(n);
    347         for(ll i = 1; i < n; i++){
    348             ll x, y;
    349             cin >> x >> y;
    350             x--;
    351             y--;
    352             v[x].push_back(y);
    353             v[y].push_back(x);
    354         }
    355  
    356         ll ans = 0;
    357         vector<ll> ss(n, 1);
    358  
    359         function<void(ll, ll)> dfs = [&](ll u, ll par){
    360  
    361             vector<ll> val;
    362             for(auto& z : v[u]) if(z != par){
    363                 dfs(z, u);
    364                 val.push_back(ss[z]);
    365                 ss[u] += ss[z];
    366             }
    367  
    368             val.push_back(n - ss[u]);
    369             assert(accumulate(val.begin(), val.end(), 0ll) == n - 1);
    370  
    371             if((ll)sqrtl(a[u]) * (ll)sqrtl(a[u]) < a[u]) return;
    372  
    373             ll sum = 0;
    374             ll pairs = 0;
    375             ll triplets = 0;
    376 
    377             for(auto& z : val){
    378                 triplets += pairs * z;
    379                 pairs += sum * z;
    380                 sum += z;
    381             }
    382 
    383             ans += pairs;
    384             ans += triplets;
    385         };
    386  
    387         dfs(0, -1);
    388  
    389         cout << ans << '\n';
    390     }
    391  
    392     return 0;
    393 }
    394 ```
    395 
    396 **Rate The Problem!**
    397 
    398 * Best Problem
    399 * Good Problem
    400 * Okay Problem
    401 * Bad Problem
    402 * Didn't Solve
    403 
    404 #### [2241F - Не очень чётно](/contest/2241/problem/F "Codeforces Round 1107 (Div. 3)")
    405 
    406 **Idea**
    407 
    408 One common way to solve these kinds of games is to first identify the losing states and then generalize their structure.
    409 
    410 Let's first consider the states where the current player has no valid moves. An obvious example is a binary string consisting entirely of `0`s or entirely of `1`s. Since a player may delete **any subsequence** with an odd number of inversions, there is a lot of freedom in choosing a move. So instead of analyzing every possible move, let us ask a simpler question: *When can Alice win immediately by deleting all `0`s or all `1`s?*
    411 
    412 Suppose Alice wants to delete all `1`s. Then the chosen subsequence must have an odd number of inversions. This is possible iff it contains at least one `0` that is preceded by an odd number of `1`s in the original string. Similarly, if Alice wants to delete all `0`s, then the chosen subsequence must contain at least one `1` that is followed by an odd number of `0`s. Both conditions can be checked in $\mathcal{O}(n)$ using prefix (or suffix) parity.
    413 
    414 Now let us consider the strings that satisfy **neither** of these conditions. Such strings must have the form
    415 
    416 $ 0(X_1)(X_2)\cdots(X_k)1, $
    417 
    418 where each $X_i$ is either `00` or `11`. The leading `0` and trailing `1` are optional. Since these endpoint characters can never affect any inversion parity, we may simply ignore them. We claim that every string of this form is a losing state.
    419 
    420 **Proof**
    421 
    422 Suppose Alice deletes a subsequence $S_1$, leaving the subsequence $S_2$.
    423 
    424 Consider any block $X_i$.
    425 
    426 * If both characters of $X_i$ end up in the same subsequence, then $X_i$ contributes an even number of inversions to that subsequence, so it does not affect the parity.
    427 * Otherwise, the two characters are split between $S_1$ and $S_2$. In this case, each subsequence receives exactly one copy of the same character, so the contribution of this block to the inversion parity is identical in both subsequences.
    428 
    429 Therefore, after ignoring every block whose two characters stay together, the remaining parts of $S_1$ and $S_2$ are identical. Hence
    430 
    431 $ \operatorname{inv}(S_1)\equiv \operatorname{inv}(S_2)\pmod 2. $
    432 
    433 Since Alice's move is valid, $\operatorname{inv}(S_1)$ is odd. Therefore, $\operatorname{inv}(S_2)$ is also odd, so Bob can simply delete the entire remaining string on his turn and win immediately.
    434 
    435 Hence, every string of the above form is a losing state.
    436 
    437 Therefore, Alice wins iff the initial string does **not** have the above form. Checking this structure is straightforward.
    438 
    439 Time Complexity: $\mathcal{O}(n)$.
    440 
    441 **Implementation**
    442 
    443 ```
    444 #include<bits/stdc++.h>
    445 using namespace std;
    446  
    447 #define ll long long
    448  
    449 int main(){
    450 
    451     ios_base::sync_with_stdio(false);
    452     cin.tie(NULL);
    453  
    454     int tt = 1;
    455     cin >> tt;
    456  
    457     while(tt--){
    458         ll n;
    459         cin >> n;
    460  
    461         string s;
    462         cin >> s;
    463 
    464         bool is = 1;
    465         int left = 0, right = n - 1;
    466 
    467         while(left < n && s[left] == '0') left++;
    468         while(right >= 0 && s[right] == '1') right--;
    469 
    470         if(left > right){
    471             cout << "Bob\n";
    472             continue;
    473         }
    474 
    475         int count = 1;
    476         for(int i = left; i < right; i++){
    477             if(s[i + 1] == s[i]) count++;
    478             else{
    479                 if(count % 2 == 1) is = 0;
    480                 count = 1;
    481             }
    482         }
    483 
    484         if(count % 2 == 1) is = 0;
    485 
    486         cout << (is ? "Bob\n" : "Alice\n");
    487     }
    488  
    489     return 0;
    490 }
    491 ```
    492 
    493 **Rate The Problem!**
    494 
    495 * Best Problem
    496 * Good Problem
    497 * Okay Problem
    498 * Bad Problem
    499 * Didn't Solve
    500 
    501 #### [2241G - Сумматоха](/contest/2241/problem/G "Codeforces Round 1107 (Div. 3)")
    502 
    503 **Idea**
    504 
    505 Let us look at what one operation really means.
    506 
    507 Suppose we are working with a subarray $[l,r]$, and let $x=a_l$. The first element is special because it never changes: every operation only uses earlier values to modify later positions, so the leftmost value stays fixed forever.
    508 
    509 Now the only thing that matters is how much freedom we have for the next elements. This is where $\text{gcd}$ enters naturally. If the current prefix has $\text{gcd}$ equal to $g$, then we claim that the next element can be changed by any multiple of $g$.
    510 
    511 **Proof**
    512 
    513 Let the array be $b$, and we are focusing on a prefix $b_1, b_2, \dots, b_{k-1}$ to modify the next element $b_k$.
    514 
    515 The allowed operation is strictly adjacent: $b_{j+1} := b_{j+1} \pm b_j$. At first glance, it seems we can only directly add $b_{k-1}$ to $b_k$. How do we add an earlier element, like $b_1$, directly to $b_k$ without permanently destroying the intermediate elements?
    516 
    517 We can "pass" values through intermediate elements. Let's look at adding $b_1$ to $b_3$ without permanently changing $b_2$:
    518 
    519 1. Add $b_1$ to $b_2 \implies b_2$ becomes $b_2 + b_1$
    520 2. Add $b_2$ to $b_3 \implies b_3$ becomes $b_3 + b_2 + b_1$
    521 3. Subtract $b_1$ from $b_2 \implies b_2$ is restored to its original value $b_2$
    522 4. Subtract $b_2$ from $b_3 \implies b_3$ becomes $(b_3 + b_2 + b_1) - b_2 = b_3 + b_1$
    523 
    524 Through this sequence, $b_2$ is perfectly restored to its original state, but $b_3$ has cleanly absorbed exactly one $+b_1$.
    525 
    526 By chaining this trick across any distance, we can propagate any prefix element $b_i$ to $b_k$. We can repeat these sequences to add or subtract $b_i$ as many times as we want. Because these operations can be done independently for each element in the prefix, the total change we can apply to $b_k$ is precisely the set of all integer linear combinations:
    527 
    528 $\Delta b_k = c_1b_1 + c_2b_2 + \dots + c_{k-1}b_{k-1}$
    529 
    530 where $c_i \in \mathbb{Z}$.
    531 
    532 Let $C$ be the set of all integer linear combinations of the prefix elements $b_1, \dots, b_{k-1}$, and let $g = \gcd(b_1, \dots, b_{k-1})$. Let $M$ be the set of all integer multiples of $g$. We need to prove that $C = M$ by showing they are subsets of each other.
    533 
    534 **1. Every linear combination is a multiple of $g$ ($C \subseteq M$)**
    535 
    536 By the definition of the greatest common divisor, $g$ divides every element $b_i$. Thus, there exist integers $q_i$ such that $b_i = q_i g$. Take any arbitrary linear combination $x \in C$:
    537 
    538 $x = \sum_{i=1}^{k-1} c_i b_i$
    539 
    540 Substitute $b_i = q_i g$ into the equation:
    541 
    542 $x = \sum_{i=1}^{k-1} c_i (q_i g) = g \sum_{i=1}^{k-1} (c_i q_i)$
    543 
    544 Since the product and sum of integers $c_i$ and $q_i$ form an integer, $x$ is an exact integer multiple of $g$. Therefore, $C \subseteq M$.
    545 
    546 **2. Every multiple of $g$ is a reachable linear combination ($M \subseteq C$)**
    547 
    548 By *Bézout's Identity*, there exist integers $u_i$ such that their linear combination exactly equals the greatest common divisor:
    549 
    550 $\sum_{i=1}^{k-1} u_i b_i = g$
    551 
    552 Take any arbitrary multiple $y \in M$, meaning $y = m g$ for some integer $m$. Substitute $g$ using Bézout's Identity:
    553 
    554 $y = m \left( \sum_{i=1}^{k-1} u_i b_i \right) = \sum_{i=1}^{k-1} (m u_i) b_i$
    555 
    556 Since $m$ and $u_i$ are integers, their product $(m u_i)$ is also an integer. This proves $y$ is a valid linear combination of the prefix elements. Therefore, $M \subseteq C$.
    557 
    558 Since $C \subseteq M$ and $M \subseteq C$, it strictly follows that $C = M$. The set of all reachable changes is exactly the set of all multiples of the prefix's $\gcd$.
    559 
    560 Now let us focus on subarrays starting at index $l$.
    561 
    562 As long as every element to the right of $a_l$ is divisible by $a_l$, the $\text{gcd}$ of the processed prefix remains exactly $a_l$ — because all seen values are multiples of $a_l$, and $a_l$ itself is present. So every such element can be moved by multiples of $a_l$, which means each of them can be made equal to $a_l$. Therefore, if the subarray never contains an element not divisible by $a_l$, then the whole subarray can be made constant, and the value of $f$ is $0$.
    563 
    564 Now define $\text{next[l]}$ as the first position $t \gt l$ such that $a_t$ is **not** divisible by $a_l$. If no such position exists, set $\text{next[l]=n+1}$.
    565 
    566 If such a position exists, we write
    567 
    568 $ r = a_t \bmod a_l. $
    569 
    570 Since $t$ is the first such position, the $\text{gcd}$ of everything before it is still $a_l$, so the value at position $t$ can only move inside its residue class modulo $a_l$. Hence, the closest it can get to $a_l$ is
    571 
    572 $ d=\min(r,\ a_l-r). $
    573 
    574 So the spread of the subarray can never go below $d$.
    575 
    576 The key observation is that the first non-divisible element already fixes the answer. The lower bound $d$ obtained from this element is tight, and no later element can increase it. Therefore, once this position appears, every longer subarray starting at $l$ has the same answer $d$.
    577 
    578 **Proof**
    579 
    580 Look at the position $t + 1$. The prefix $\text{gcd}$ at this position will be $g = \text{gcd}(a_l, a_t)$. Since $g$ divides both $a_l$ and $a_t$, it also divides $a_t \bmod a_l$ and $a_l - a_t \bmod a_l$. Therefore, $g \mid d$.
    581 
    582 From this point onward, every later element can be modified using multiples of a $\text{gcd}$, which is at most $g$. Therefore, every later element can be adjusted in steps whose size divides $d$.
    583 
    584 Now, fix the value at position $t$ so that its distance from $a_l$ is exactly $d$. Since every future modification is performed using multiples of divisors of $d$, every later element can be moved into the interval of length $d$ determined by these two values. Consequently, no later position can force the spread to become larger than $d$.
    585 
    586 Therefore, the first non-divisible element completely determines the answer: once position $t$ appears, every longer subarray contributes the same value $d$ to the final answer.
    587 
    588 Hence, for a fixed $l$:
    589 
    590 * for every $r \lt \text{next}[l]$, we have $f([a_l,\dots,a_r])=0$;
    591 * for every $r\ge \text{next}[l]$, we have
    592 
    593 $ f([a_l,\dots,a_r]) = \min \bigl(a_{\text{next}[l]} \bmod a_l,\ a_l-(a_{\text{next}[l]} \bmod a_l)\bigr). $
    594 
    595 So, once $\text{next[l]}$ is found, all longer subarrays starting at $l$ contribute the same value. That makes counting easy. The number of subarrays starting at $l$ that contain this position is $n-t+1$. So the contribution from index $l$ is
    596 
    597 $ (n-t+1) \cdot \min \bigl(a_t\bmod a_l,\ a_l-(a_t\bmod a_l)\bigr). $
    598 
    599 Now we only need to find $\text{next[l]}$ for every $l$. This can be done with a monotonic stack while scanning from left to right. The stack stores indices whose first non-divisible element has not been found yet. In detail, when we are at position $i$, if
    600 
    601 $ a_i \bmod a_{\text{top}} \ne 0, $
    602 
    603 then we have $i = \text{next[top]}$. Why? Because if any earlier position had already broken divisibility for that index, it would already have been removed from the stack. So we can finalize its contribution immediately and pop it. This way, each index is pushed once and popped once, so the whole procedure is linear.
    604 
    605 Time Complexity: $\mathcal{O}(n)$.
    606 
    607 Note that one can also find $\text{next[l]}$ for every index $l$ by performing binary search using a sparse table to store $\text{gcd}$, leading to an $\mathcal{O}(n \cdot \log n \cdot \log a)$ solution. These implementations are also intended to pass.
    608 
    609 **Implementation**
    610 
    611 ```
    612 #include<bits/stdc++.h>
    613 using namespace std;
    614  
    615 #define ll long long
    616 typedef __int128 int128;
    617 
    618 std::ostream& operator<<(std::ostream& os, int128 t) {
    619     if (t == 0) return os << "0";
    620     if (t < 0) {
    621         os << "-";
    622         t = -t;
    623     }
    624     int a[50], i = 0;
    625     while (t > 0) {
    626         a[i++] = t % 10;
    627         t /= 10;
    628     }
    629     for (int j = i - 1; j >= 0; j--) {
    630         os << (char)(a[j] + '0');
    631     }
    632     return os;
    633 }
    634 
    635 int main(){
    636     ios_base::sync_with_stdio(false);
    637     cin.tie(NULL);
    638  
    639     int tt = 1;
    640     cin >> tt;
    641  
    642     while(tt--){
    643         ll n;
    644         cin >> n;
    645  
    646         vector<ll> a(n);
    647         for(auto& z : a) cin >> z;
    648 
    649         int128 ans = 0;
    650         stack<ll> s;
    651 
    652         for(int i = 0; i < n; i++){
    653             while(!s.empty() && a[i] % a[s.top()] > 0){
    654                 ans += (int128)1 * (n - i) * min(a[i] % a[s.top()], a[s.top()] - a[i] % a[s.top()]);
    655                 s.pop();
    656             }
    657             s.push(i);
    658         }
    659 
    660         cout << ans << '\n';
    661     }
    662  
    663     return 0;
    664 }
    665 ```
    666 
    667 **Rate The Problem!**
    668 
    669 * Best Problem
    670 * Good Problem
    671 * Okay Problem
    672 * Bad Problem
    673 * Didn't Solve