codeforces-scrape

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

2094.md (23028B)


      1 Source: https://codeforces.com/blog/entry/141796
      2 
      3 **Rating Predictions**
      4 
      5 | Predictor | A | B | C | D | E | F | G | H |
      6 | --- | --- | --- | --- | --- | --- | --- | --- | --- |
      7 | [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED") | 800 | 800 | 800 | 1000 | 1200 | 1300 | 1600 | 1800 |
      8 | [Dominater069](/profile/Dominater069 "International Grandmaster Dominater069") | 800 | 800 | 800 | 900 | 1200 | 1200 | 1600 | 1600 |
      9 | [reirugan](/profile/reirugan "Candidate Master reirugan") | 800 | 800 | 800 | 900 | 1500 | 1500 | 1700 | 1700 |
     10 | [macaquedev](/profile/macaquedev "Expert macaquedev") | 800 | 800 | 800 | 900 | 1600 | 900 | 1800 | — |
     11 | [Filikec](/profile/Filikec "Expert Filikec") | 800 | 800 | 800 | 900 | 1300 | 1500 | 1700 | 1800 |
     12 | [Edeeva](/profile/Edeeva "Master Edeeva") | 800 | 800 | 800 | 1000 | 1300 | 1600 | 1700 | 1900 |
     13 | [yoru_sacri](/profile/yoru_sacri "Candidate Master yoru_sacri") | 800 | 800 | 800 | 900 | 1400 | 1700 | 1900 | 1900 |
     14 | [kevlu8](/profile/kevlu8 "Expert kevlu8") | 800 | 800 | 800 | 900 | 1600 | 1400 | 1700 | — |
     15 | [AG-88301](/profile/AG-88301 "Specialist AG-88301") | 800 | 800 | 800 | 800 | 1400 | 1500 | — | — |
     16 | [-firefly-](/profile/-firefly- "Master -firefly-") | 800 | 800 | 800 | 1000 | 1300 | 1200 | 1800 | 2000 |
     17 | [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv") | 800 | 800 | 800 | 1000 | 1200 | 3500 | 1900 | 2000 |
     18 | [temporary1](/profile/temporary1 "Master temporary1") | 800 | 800 | 800 | 1000 | 1400 | 1500 | 1500 | 2000 |
     19 
     20 Thanks to [reirugan](/profile/reirugan "Candidate Master reirugan") for helping write the editorials.
     21 
     22 #### [2094A - Trippi Troppi](/contest/2094/problem/A "Codeforces Round 1017 (Div. 4)")
     23 
     24 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED")
     25 
     26 **Solution**
     27 
     28 This can be solved by printing the zero-th index of each string in sequence. For example, suppose your strings are $a$, $b$, and $c$. Then in C++, you can use `cout << a[0] << b[0] << c[0] << '\n';`, and similarly, in Python you can use `print(a[0] + b[0] + c[0])`. See your preferred language's syntax for how to obtain a given indexed character from a string.
     29 
     30 **Code**
     31 
     32 ```
     33 t = int(input())
     34 for _ in range(t):
     35     inp = input()
     36     for w in inp.split():
     37         print(w[0],end="")
     38     print()
     39 ```
     40 
     41 **Rate The Problem!**
     42 
     43 * Good Problem
     44 * Okay Problem
     45 * Bad Problem
     46 * Didn't Solve
     47 
     48 #### [2094B - Bobritto Bandito](/contest/2094/problem/B "Codeforces Round 1017 (Div. 4)")
     49 
     50 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED")
     51 
     52 **Hint**
     53 
     54 What is the condition for $l'$ and $r'$ to be valid?
     55 
     56 **Answer**
     57 
     58 We must have $r' - l' = m$ and $l\leq l' \leq 0 \leq r'\leq r$.
     59 
     60 **Solution**
     61 
     62 The problem reduces to finding $l'$ and $r'$ such that $r' - l' = m$ and $l\leq l' \leq 0 \leq r'\leq r$. There are several different approaches; two are outlined below.
     63 
     64 One approach which runs in $O(1)$ time is to case on whether $m\leq r$. If $m\leq r$, we can choose $l' = 0$ and $r' = m$, and then we see that $r' - l' = m - 0 = m$ and $l \leq 0 \leq 0 \leq m \leq r$ as desired. If $m \gt r$, we can choose $l' = r-m$ and $r' = r$, and then we see that $r' - l' = r - (r-m) = m$ and $l \leq r-m \leq 0 \leq r \leq r$, where $l \leq r-m$ holds because $r-l = n \geq m$.
     65 
     66 An alternative approach which runs in $O(m)$ time is to simply simulate the process; expand in an arbitrary direction which satisfies the desired inequalities until $r' - l' = m$.
     67 
     68 **Code**
     69 
     70 ```
     71 #include <bits/stdc++.h>
     72 using namespace std;
     73 #define int long long
     74 
     75 void solve() {
     76     int n, m, l, r; cin >> n >> m >> l >> r;
     77     int diff = n - m;
     78     l = abs(l);
     79     if (l >= diff) {
     80         l -= diff;
     81         diff = 0;
     82     }
     83     else {
     84         diff -= l;
     85         l = 0;
     86     }
     87     cout << -l << " " << r - diff << '\n';
     88 }
     89 
     90 signed main() {
     91     ios_base::sync_with_stdio(0);
     92     cin.tie(0);
     93     int t; cin >> t;
     94     while (t--) solve();
     95     return 0;
     96 }
     97 ```
     98 
     99 **Rate The Problem!**
    100 
    101 * Good Problem
    102 * Okay Problem
    103 * Bad Problem
    104 * Didn't Solve
    105 
    106 #### [2094C - Brr Brrr Patapim](/contest/2094/problem/C "Codeforces Round 1017 (Div. 4)")
    107 
    108 Problem Credits: [cry](/profile/cry "International Master cry")
    109 
    110 **Hint**
    111 
    112 How can we find $p_i$ for $2\leq i\leq n$? How can we find $p_i$ for $n+1\leq i\leq 2n$?
    113 
    114 **Answer**
    115 
    116 For $2\leq i\leq n$, we can find $p_i$ by checking $G_{1, i-1}$. For $n+1\leq i\leq 2n$, we can find $p_i$ by checking $G_{n, i-n}$.
    117 
    118 **Solution**
    119 
    120 Observe that for all $2\leq i\leq n$, we can find $p_i$ by checking $G_{1, i-1}$. Then for all $n+1\leq i\leq 2n$, we can find $p_i$ by checking $G_{n, i-n}$. Now, we only have to find the value of $p_1$. However, each value from $1$ to $2n$ must appear exactly once in $p$. Thus, we can simply find the value which has not appeared yet, and choose that as $p_1$. This can be done by storing which values have been seen in a boolean array, and then finding which one remains false.
    121 
    122 **Code**
    123 
    124 ```
    125 #include <bits/stdc++.h>
    126 using namespace std;
    127 #define int long long
    128 
    129 void solve() {
    130     int n; cin >> n;
    131     vector<int> ans(2*n+1, 0);
    132     vector<bool> used(2*n+1, false);
    133     for (int i = 1; i <= n; i++) {
    134         for (int j = 1; j <= n; j++) {
    135             int x; cin >> x;
    136             ans[i + j] = x;
    137             used[x] = true;
    138         }
    139     }
    140     for (int i = 1; i <= 2 * n; i++) {
    141         if (ans[i] != 0) cout << ans[i] << " ";
    142         else {
    143             for (int j = 1; j <= n * 2; j++) {
    144                 if (!used[j]) {
    145                     used[j] = true;
    146                     cout << j << " ";
    147                     break;
    148                 }
    149             }
    150         }
    151     }
    152     cout << "\n";
    153 }
    154 
    155 signed main() {
    156     ios_base::sync_with_stdio(0);
    157     cin.tie(0);
    158     int t; cin >> t;
    159     while (t--) solve();
    160     return 0;
    161 }
    162 ```
    163 
    164 **Rate The Problem!**
    165 
    166 * Good Problem
    167 * Okay Problem
    168 * Bad Problem
    169 * Didn't Solve
    170 
    171 #### [2094D - Tung Tung Sahur](/contest/2094/problem/D "Codeforces Round 1017 (Div. 4)")
    172 
    173 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED")
    174 
    175 **Hint**
    176 
    177 What would happen if $s_1$ consists of only $L$?
    178 
    179 **Answer**
    180 
    181 In this case, the answer is yes if and only if $|s_1| \leq |s_2| \leq 2|s_1|$. Now try to generalize this.
    182 
    183 **Solution**
    184 
    185 First, let us consider a simpler case of the problem: suppose that there is only $L$ in both $s_1$ and $s_2$. Then it is clear that the answer is yes if and only if $|s_1| \leq |s_2| \leq 2|s_1|$. If this holds (in particular, we also necessitate that $s_1$ and $s_2$ consist of only a single character, and the same character), we will call $s_2$ an extension of $s_1$.
    186 
    187 Now, observe that the problem given is simply the simpler version, repeated several times alternating between $L$ and $R$. So we can partition $s_1$ into "blocks" (where we define a block to be a maximal group of contiguous identical characters). Then the answer is yes if and only if $s_2$ is the concatenation of extensions of blocks in $s_1$. For example, consider $s_1 = LLLLLRL$. We see that this consists of five $L$s, one $R$, and one $L$. So the answer is yes if and only if $s_2$ consists of between five and ten $L$s (inclusive), between one and two $R$s, and between one and two $L$ 's, concatenated in that order.
    188 
    189 **Code**
    190 
    191 ```
    192 #include <bits/stdc++.h>
    193 using namespace std;
    194 #define int long long
    195 
    196 void solve() {
    197     string a, b; cin >> a >> b;
    198     int n = a.size();
    199     int m = b.size();
    200     if (m < n || m > 2 * n || a[0] != b[0]) {
    201         cout << "NO\n";
    202         return;
    203     }
    204     vector<int> aa, bb;
    205     int cnt = 1;
    206     for (int i = 1; i < n; i++) {
    207         if (a[i] != a[i-1]) {
    208             aa.push_back(cnt);
    209             cnt = 1;
    210         }
    211         else cnt++;
    212     }
    213     aa.push_back(cnt);
    214     cnt = 1;
    215     for (int i = 1; i < m; i++) {
    216         if (b[i] != b[i-1]) {
    217             bb.push_back(cnt);
    218             cnt = 1;
    219         }
    220         else cnt++;
    221     }
    222     bb.push_back(cnt);
    223     if (aa.size() != bb.size()) {
    224         cout << "NO\n";
    225         return;
    226     }
    227     n = aa.size();
    228     for (int i = 0; i < n; i++) {
    229         if (aa[i] > bb[i] || aa[i] * 2 < bb[i]) {
    230             cout << "NO\n";
    231             return;
    232         }
    233     }
    234     cout << "YES\n";
    235 }
    236 
    237 signed main() {
    238     ios_base::sync_with_stdio(0);
    239     cin.tie(0);
    240     int t; cin >> t;
    241     while (t--) solve();
    242     return 0;
    243 }
    244 ```
    245 
    246 **Rate The Problem!**
    247 
    248 * Good Problem
    249 * Okay Problem
    250 * Bad Problem
    251 * Didn't Solve
    252 
    253 #### [2094E - Boneca Ambalabu](/contest/2094/problem/E "Codeforces Round 1017 (Div. 4)")
    254 
    255 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED")
    256 
    257 **Hint 1**
    258 
    259 Consider each bit independently.
    260 
    261 **Hint 2**
    262 
    263 Suppose we fix $k$. How can we compute the desired sum quickly? Note that this may require preprocessing.
    264 
    265 **Solution**
    266 
    267 Here, it suffices to consider each bit independently, because addition is both commutative and associative. For $0\leq i \lt 30$, let $cnt_i$ denote the number of elements of $a$ which have the $i$-th bit set (where bits are indexed from the least significant bit being the $0$-th bit); note that these can be found in $O(30n)$ time (more generally, we need $O(\log\max{a_i})$ operations per element).
    268 
    269 Now, suppose we choose a particular $k$. Then we can find the sum $(a_k\oplus a_1) + (a_k\oplus a_2) \dots + (a_k\oplus a_n)$ as follows: for a given bit position $i$, the number of elements $a_j$ such that $a_k \oplus a_j$ has the $i$-th bit set will be $cnt_i$ if the $i$-th bit of $a_k$ is not set, and $n-cnt_i$ if the $i$-th bit of $a_k$ is set. So we can simply add $cnt_i \cdot 2^i$ to our sum if the $i$-th bit of $a_k$ is not set, and add $(n-cnt_i) \cdot 2^i$ to our sum if the $i$-th bit of $a_k$ is set.
    270 
    271 This allows us to compute $(a_k\oplus a_1) + (a_k\oplus a_2) \dots + (a_k\oplus a_n)$ for any $k$ in $O(30)$ time, so we can now compute this sum for all $k$ in $O(30n)$ time and output the maximum.
    272 
    273 **Code**
    274 
    275 ```
    276 #include <bits/stdc++.h>
    277 using namespace std;
    278 #define int long long
    279 
    280 void solve() {
    281     int n; cin >> n;
    282     int arr[n+1];
    283     vector<int> cnt(30, 0);
    284     for (int i = 1; i <= n; i++) {
    285         cin >> arr[i];
    286         for (int j = 0; j < 30; j++) {
    287             cnt[j] += ((arr[i] >> j) & 1);
    288         }
    289     }
    290     int ans = 0;
    291     for (int i = 1; i <= n; i++) {
    292         int tot = 0;
    293         for (int j = 0; j < 30; j++) {
    294             bool f = ((arr[i] >> j) & 1);
    295             if (f) tot += (1 << j) * (n - cnt[j]);
    296             else tot += (1 << j) * cnt[j];
    297         }
    298         ans = max(ans, tot);
    299     }
    300     cout << ans << "\n";
    301 }
    302 
    303 signed main() {
    304     ios_base::sync_with_stdio(0);
    305     cin.tie(0);
    306     int t; cin >> t;
    307     while (t--) solve();
    308     return 0;
    309 }
    310 ```
    311 
    312 **Rate The Problem!**
    313 
    314 * Good Problem
    315 * Okay Problem
    316 * Bad Problem
    317 * Didn't Solve
    318 
    319 #### [2094F - Trulimero Trulicina](/contest/2094/problem/F "Codeforces Round 1017 (Div. 4)")
    320 
    321 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED")
    322 
    323 **Hint**
    324 
    325 What would happen if we tried outputting the numbers $1, \dots, k, 1, \dots, k, \dots$ in the natural reading order? For example, for $n=3$, $m=4$, and $k=6$, we would output the following:
    326 
    327 |  |  |  |  |
    328 | --- | --- | --- | --- |
    329 | 1 | 2 | 3 | 4 |
    330 | 5 | 6 | 1 | 2 |
    331 | 3 | 4 | 5 | 6 |
    332 
    333 In which cases does this fail?
    334 
    335 **Answer**
    336 
    337 This fails if and only if $m$ is a multiple of $k$, because we see that horizontally adjacent elements differ by $1\pmod k$ and vertically adjacent elements differ by $m\pmod k$. Now try to resolve this case.
    338 
    339 **Solution**
    340 
    341 There are many working constructions for this problem; one of them is to case on whether or not $m$ is a multiple of $k$.
    342 
    343 Suppose $m$ is not a multiple of $k$. For example, consider the second sample, where $n=3$, $m=4$, and $k=6$. Then we can output the numbers $1, \dots, k, 1, \dots, k, \dots$ in the natural reading order, as follows:
    344 
    345 |  |  |  |  |
    346 | --- | --- | --- | --- |
    347 | 1 | 2 | 3 | 4 |
    348 | 5 | 6 | 1 | 2 |
    349 | 3 | 4 | 5 | 6 |
    350 
    351 and we see that any two horizontally adjacent elements differ by $1\pmod k$, whereas any two vertically adjacent elements differ by $m\pmod k$, so no two adjacent elements are the same, as desired.
    352 
    353 Now, suppose $m$ is a multiple of $k$. For example, consider the case $n=4$, $m=6$, and $k=3$. Suppose we were to try the above strategy, then we get:
    354 
    355 |  |  |  |  |  |  |
    356 | --- | --- | --- | --- | --- | --- |
    357 | 1 | 2 | 3 | 1 | 2 | 3 |
    358 | 1 | 2 | 3 | 1 | 2 | 3 |
    359 | 1 | 2 | 3 | 1 | 2 | 3 |
    360 | 1 | 2 | 3 | 1 | 2 | 3 |
    361 
    362 which doesn't work, since vertically adjacent elements are the same. We can fix this by cyclically shifting every other row as follows:
    363 
    364 |  |  |  |  |  |  |
    365 | --- | --- | --- | --- | --- | --- |
    366 | 1 | 2 | 3 | 1 | 2 | 3 |
    367 | 2 | 3 | 1 | 2 | 3 | 1 |
    368 | 1 | 2 | 3 | 1 | 2 | 3 |
    369 | 2 | 3 | 1 | 2 | 3 | 1 |
    370 
    371 and we see that any two horizontally adjacent elements differ by $1\pmod k$ as before, whereas any two vertically adjacent elements also differ by $1\pmod k$, so no two adjacent elements are the same, as desired.
    372 
    373 **Code**
    374 
    375 ```
    376 import sys
    377 input = sys.stdin.readline
    378 for _ in range(int(input())):
    379     n,m,k = map(int,input().split())
    380     LAST = [-1 for _ in range(m)]
    381     for i in range(n):
    382         shift = False
    383         CUR = [0 for _ in range(m)]
    384         for j in range(m):
    385             elm = ((i * m + j) % k) + 1
    386             if elm == LAST[j]:
    387                 shift = True
    388             CUR[j] = elm
    389         if shift:
    390             CUR = [CUR[(j+1)%m] for j in range(m)]
    391         print(*CUR)
    392         LAST = CUR
    393 ```
    394 
    395 **Rate The Problem!**
    396 
    397 * Good Problem
    398 * Okay Problem
    399 * Bad Problem
    400 * Didn't Solve
    401 
    402 #### [2094G - Chimpanzini Bananini](/contest/2094/problem/G "Codeforces Round 1017 (Div. 4)")
    403 
    404 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Master Proof_by_QED"), [cry](/profile/cry "International Master cry")
    405 
    406 **Hint 1**
    407 
    408 Note that reversing an array then pushing an element to the back is similar to simply pushing an element to the front. Thus, we would like to push elements to both ends of the array. What data structure supports this?
    409 
    410 **Answer**
    411 
    412 A deque is the most natural choice to use. Most languages, including C++, Java, and Python, include deques in their standard library, so you likely do not have to implement it yourself.
    413 
    414 **Hint 2**
    415 
    416 What other values do we need to maintain in order to keep track of score?
    417 
    418 **Answer**
    419 
    420 It suffices to keep track of the current score, the score of the array if it were backwards, the size of the array, and the sum of the array.
    421 
    422 **Solution**
    423 
    424 We can solve this using a deque. Let $score$ denote the current score, and $rscore$ denote the score of the array if it were backwards. Let $size$ denote the size of the array, and $sum$ denote the sum of the array. Then we consider how these three values change as each operation is performed.
    425 
    426 Suppose operation 1 is performed. This is equivalent to popping the back element of the array and pushing it in the front. When you pop the back element of the array, $score$ decreases by $a_n \cdot size$. Then when you push it to the front, $score$ increases by $sum$ because $a_n$ is pushed to the first spot and every element from $a_1$ to $a_{n-1}$ moves forward one spot. Notice that $rscore$ changes in the reverse way; this is equivalent to popping the front element of the array and pushing it to the back. When you pop the front element of the array, $rscore$ decreases by $sum$, and when you push it to the back, $rscore$ increases by $a_n \cdot size$. Note that $size$ and $sum$ remain unchanged.
    427 
    428 Suppose operation 2 is performed. Then we swap $score$ and $rscore$, and we also want to "reverse" the array. However, it is costly to entirely reverse the deque. Instead, we will set a flag to indicate that the array has been reversed (and similarly, if the flag is already set, we will unset it). If the flag is set, we simply switch the front and back ends whenever we access or modify the deque while performing operations 1 or 3.
    429 
    430 Suppose operation 3 is performed. Then we see that $size$ increases by $1$ and $sum$ increases by $k$. Then $score$ increases by $k \cdot size$ and $rscore$ increases by $sum$ (using the new value of $sum$), by identical reasoning to that in operation 1.
    431 
    432 Additional optimization: we don't actually have to maintain $rscore$; we can obtain it with the expression: $(n+1)\sum_{i=1}^na_i-score$. This is because $score + rscore = (n+1)\sum_{i=1}^na_i$ since the $i$-th term is counted $i$ times in $score$ and $n+1-i$ times in $rscore$.
    433 
    434 **Code**
    435 
    436 ```
    437 #include <bits/stdc++.h>
    438 using namespace std;
    439 #define int long long
    440 
    441 void solve() {
    442     int norm = 0, rev = 0;
    443     int q; cin >> q;
    444     int tot = 0;
    445     int n = 0;
    446     deque<int> qNorm, qRev;
    447     int p = 0;
    448     while (q--) {
    449         int s; cin >> s;
    450         if (s == 1) {
    451             int last = qNorm.back();
    452             qNorm.pop_back();
    453             qNorm.push_front(last);
    454             norm += (tot - last);
    455             norm -= last * n;
    456             norm += last;
    457 
    458             last = qRev.front();
    459             qRev.pop_front();
    460             qRev.push_back(last);
    461             rev -= (tot - last);
    462             rev += last * n;
    463             rev -= last;
    464         }
    465         else if (s == 2) {
    466             swap(rev, norm);
    467             swap(qNorm, qRev);
    468         }
    469         else if (s == 3) {
    470             n++;
    471             int k; cin >> k;
    472             qNorm.push_back(k);
    473             qRev.push_front(k);
    474             norm += k * n;
    475             rev += tot;
    476             rev += k;
    477             tot += k;
    478         }
    479         cout << norm << "\n";
    480     }
    481 }
    482 
    483 signed main() {
    484     ios_base::sync_with_stdio(0);
    485     cin.tie(0);
    486     int t; cin >> t;
    487     while (t--) solve();
    488     return 0;
    489 }
    490 ```
    491 
    492 **Rate The Problem!**
    493 
    494 * Good Problem
    495 * Okay Problem
    496 * Bad Problem
    497 * Didn't Solve
    498 
    499 #### [2094H - La Vaca Saturno Saturnita](/contest/2094/problem/H "Codeforces Round 1017 (Div. 4)")
    500 
    501 Problem Credits: [cry](/profile/cry "International Master cry")
    502 
    503 **Hint 1**
    504 
    505 What must the value of $a[i]$ be in order for $k$ to change?
    506 
    507 **Answer**
    508 
    509 $a[i]$ must be a divisor of $k$.
    510 
    511 **Hint 2**
    512 
    513 Can we use this to bound the number of times $k$ changes?
    514 
    515 **Answer**
    516 
    517 For each divisor $d$ of $k$, $k$ can only change once, because after the first iteration with $a[i] = d$, $k$ is no longer divisible by $d$. Thus, the number of times $k$ changes is bounded by the number of divisors of $k$.
    518 
    519 **Solution**
    520 
    521 Consider a particular query. We make the following two observations: first, the value of $k$ only changes if $a[i]$ is a divisor of $k$, and second, if there exists $a[i_1] = a[i_2]$ with $l\leq i_1 \lt i_2 \leq r$, then the value of $k$ will not change at $i=i_2$ (because after the iteration $i=i_1$, we have that $k$ is no longer divisible by $a[i_2]$).
    522 
    523 This allows us to bound the number of times $k$ changes by $d(k)$, where $d(k)$ is the number of divisors of $k$. Note that the divisors of $d(k)$ can be found in $O(\sqrt{k})$ time by checking if $a$ divides $k$ for every $a$ from $2$ to $\sqrt{k}$, and if so, $a$ and $\frac{k}{a}$ are both divisors of $k$. Furthermore, at the scale constrained by the problem bounds, $d(k)$ is around $O(\sqrt[3]{k})$, so we only have to update $k$ at most $O(\sqrt[3]{k})$ times.
    524 
    525 Now, we would like to find the first time each divisor of $k$ appears in $a[l], \dots, a[r]$. This can be done by storing the array $a$ in a map, where each value is mapped to a vector of indices where that values appears. Then for a given divisor of $k$, we can use `lower_bound()` (or generally, binary search) to find the smallest index at or after $l$ where this divisor appears, and we can check if it is no greater than $r$.
    526 
    527 Now, we have a list of indices at which $k$ might change. So, suppose that $k$ changes to $k'$ at index $i_1$, and then changes to $k' '$ at index $i_2$ (and these are adjacent changes). Then we know that we have a value of $k'$ from $i=i_1$ to $i_2-1$, so we can add $k' \cdot (i_2 - i_1)$ to $ans$. We can then do this for all changes. This allows us to solve the problem in $O(n\log{n})$ preprocessing time and $O(\sqrt{k} + d(k)\log{n})$ time per query.
    528 
    529 There are a few ways to optimize the runtime further, if your implementation is too slow. We can use a vector (of vectors) instead of a map, since $A = \max a_i = 10^5$ is reasonably small. Note that instantiating a vector of this size in every test case is too slow, so you may have to instantiate it globally and clear the vectors that were used after each test case.
    530 
    531 Another optimization is to preprocess divisors instead of computing them on the spot. We can compute and store the divisors of all integers $2\leq a_i\leq 10^5$ in $O(A\log A)$ time in a vector of vectors where $divisor[a_i]$ contains all divisors of $a_i$ as follows: for all $2\leq i\leq A$, we push $i$ into $divisors[j]$ for all multiples $j$ of $i$. (The runtime follows from the fact that there are $\lfloor\frac{A}{i}\rfloor$ multiples of $i$ which are at most $A$, so across all $i$, we have at most $\frac{A}{1} + \frac{A}{2} + \cdots + \frac{A}{A} = A(\frac{1}{1} + \cdots + \frac{1}{A}) = AH(A) = O(A\log A)$ computations). This allows us to remove the $\sqrt{k}$ term in the runtime of each query.
    532 
    533 **Code**
    534 
    535 ```
    536 #include <bits/stdc++.h>
    537 using namespace std;
    538 #define int long long
    539 
    540 void solve() {
    541     map<int, vector<int>> pos;
    542     map<int, int> ptr;
    543     int n, q; cin >> n >> q;
    544     int arr[n+1];
    545     for (int i = 1; i <= n; i++) {
    546         cin >> arr[i];
    547         pos[arr[i]].push_back(i);
    548         ptr[arr[i]] = 0;
    549     }
    550     vector<tuple<int, int, int, int>> qr(q);
    551     int c = 0;
    552     for (auto &[l, r, v, i]: qr) {
    553         cin >> v >> l >> r;
    554         i = c++;
    555     }
    556     vector<int> anss(q);
    557     sort(qr.begin(), qr.end());
    558     int prevL = 1;
    559     for (auto [l, r, v, idd]: qr) {
    560         for (int j = prevL; j < l; j++) {
    561             ptr[arr[j]]++;
    562         }
    563         prevL = l;
    564         vector<pair<int, int>> facts;
    565         for (int i = 1; i * i <= v; i++) {
    566             if (v % i == 0) {
    567                 int fact1 = v / i;
    568                 if (!(pos[fact1].size() == 0 || ptr[fact1] >= pos[fact1].size() || pos[fact1][ptr[fact1]] > r || fact1 == 1)) {
    569                     facts.push_back({pos[fact1][ptr[fact1]], fact1});
    570                 }
    571                 int fact2 = i;
    572                 if (fact2 == fact1) continue;
    573                 if (!(pos[fact2].size() == 0 || ptr[fact2] >= pos[fact2].size() || pos[fact2][ptr[fact2]] > r || fact2 == 1)) {
    574                     facts.push_back({pos[fact2][ptr[fact2]], fact2});
    575                 }
    576             }
    577         }
    578         sort(facts.begin(), facts.end());
    579         int pr = l;
    580         int ans = 0;
    581         for (auto [idx, val]: facts) {
    582             int rr = idx - pr;
    583             ans += v * rr;
    584             while (v % val == 0) v /= val;
    585             pr = idx;
    586         }
    587         if (facts.empty()) ans = v * (r - l + 1);
    588         else ans += (r - pr + 1) * v;
    589         anss[idd] = ans;
    590     }
    591     for (int i = 0; i < q; i++) cout << anss[i] << "\n";
    592 }
    593 
    594 signed main() {
    595     ios_base::sync_with_stdio(0);
    596     cin.tie(0);
    597     int t; cin >> t;
    598     while (t--) solve();
    599     return 0;
    600 }
    601 ```
    602 
    603 **Rate The Problem!**
    604 
    605 * Good Problem
    606 * Okay Problem
    607 * Bad Problem
    608 * Didn't Solve