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