codeforces-scrape

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

2153.md (35433B)


      1 Source: https://codeforces.com/blog/entry/147264
      2 
      3 ### [2153A - Circle of Apple Trees](/contest/2153/problem/A "Codeforces Round 1057 (Div. 2)")
      4 
      5 **Hint 1**
      6 
      7 You can't eat two apples of the same beauty value.
      8 
      9 **Hint 2**
     10 
     11 Is there a way to eat apples of all kinds of beauty values that appearred?
     12 
     13 **Solution**
     14 
     15 First of all, since the beauty values of the apples you eat are in strictly increasing order, any two of them have different beauty values.
     16 
     17 So, for each beauty value, you can eat at most one apple.
     18 
     19 In fact, it can be shown that it is always possible to eat exactly one apple of each beauty value. Let's say all the distinct beauty values are $v_1,v_2,\ldots,v_k\ (v_1\lt v_2\lt\ldots\lt v_k)$. You can eat one apple of beauty value $v_i$ during the $i$-th time you move along the full circle.
     20 
     21 Therefore, the answer is the number of distinct numbers in beauty values. The time complexity is $\mathcal{O}(n)$.
     22 
     23 **Code (C++, maomao90)**
     24 
     25 ```
     26 #include <bits/stdc++.h>
     27 using namespace std;
     28  
     29 int t, n;
     30  
     31 int main() {
     32     cin >> t;
     33  
     34     while (t--) {
     35         cin >> n;
     36         
     37         set<int> st;
     38         for (int i = 0; i < n; i++) {
     39             int x;
     40             cin >> x;
     41             st.insert(x);
     42         }
     43  
     44         cout << (int) st.size() << '\n';
     45     }
     46  
     47     return 0;
     48 }
     49 ```
     50 
     51 **Code (Pypy3.10, Little_Sheep_Yawn)**
     52 
     53 ```
     54 import sys
     55 input = lambda: sys.stdin.readline().strip()
     56 
     57 t = int(input())
     58 outs = []
     59  
     60 for _ in range(t):
     61     n = int(input())
     62     nums = list(map(int, input().split()))
     63     # There can be hash collisions, but n is small enough.
     64     outs.append(len(set(nums)))
     65  
     66 print('\n'.join(map(str, outs)))
     67 ```
     68 
     69 ### [2153B - Bitwise Reversion](/contest/2153/problem/B "Codeforces Round 1057 (Div. 2)")
     70 
     71 **Hint**
     72 
     73 Consider each bit of the numbers separately.
     74 
     75 **Solution**
     76 
     77 Different bits don't interfere with one another when you do bitwise operations. So, for each bit $k$, we can iterate over $2^3$ possibilities of $a_k = \mathtt{0} \text{ or } \mathtt{1}$, $b_k = \mathtt{0} \text{ or } \mathtt{1}$, and $c_k = \mathtt{0} \text{ or } \mathtt{1}$, and check whether it is consistent with the given numbers.
     78 
     79 The time complexity for each test case is $\mathcal{O}(\log \max(x, y, z))$.
     80 
     81 **Code (C++, maomao90)**
     82 
     83 ```
     84 #include <bits/stdc++.h>
     85 using namespace std;
     86  
     87 using ll = long long;
     88  
     89 const int MAXL = 60;
     90  
     91 int t;
     92 ll x, y, z;
     93  
     94 int main() {
     95     cin >> t;
     96     while (t--) {
     97         cin >> x >> y >> z;
     98         ll a = 0, b = 0, c = 0;
     99         bool ans = true;
    100         for (int l = MAXL - 1; l >= 0; l--) {
    101             ll bit_x = x >> l & 1, bit_y = y >> l & 1, bit_z = z >> l & 1;
    102             bool found = false;
    103             for (ll bit_a : {0, 1}) {
    104                 for (ll bit_b : {0, 1}) {
    105                     for (ll bit_c : {0, 1}) {
    106                         if ((bit_a & bit_b) == bit_x &&
    107                             (bit_b & bit_c) == bit_y &&
    108                             (bit_a & bit_c) == bit_z) {
    109                             found = true;
    110                             a |= bit_a << l;
    111                             b |= bit_b << l;
    112                             c |= bit_c << l;
    113                             break;
    114                         }
    115                     }
    116                     if (found) {
    117                         break;
    118                     }
    119                 }
    120                 if (found) {
    121                     break;
    122                 }
    123             }
    124             if (!found) {
    125                 ans = false;
    126                 break;
    127             }
    128         }
    129         if (!ans) {
    130             cout << "NO\n";
    131         } else {
    132             assert((a & b) == x);
    133             assert((b & c) == y);
    134             assert((a & c) == z);
    135             cout << "YES\n";
    136         }
    137     }
    138     return 0;
    139 }
    140 ```
    141 
    142 **Code (Pypy3.10, Little_Sheep_Yawn, using the bonus)**
    143 
    144 ```
    145 import sys
    146 input = lambda: sys.stdin.readline().strip()
    147 
    148 t = int(input())
    149 outs = []
    150  
    151 for _ in range(t):
    152     x, y, z = map(int, input().split())
    153     
    154     a = x | z
    155     b = x | y
    156     c = y | z
    157     
    158     outs.append('YES' if a & b == x and b & c == y and a & c == z else 'NO')
    159  
    160 print('\n'.join(outs))
    161 ```
    162 
    163 **Bonus**
    164 
    165 You just need to check whether $(a,b,c)=(x|z,x|y,y|z)$ is a valid solution, where $|$ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR). Why?
    166 
    167 ### [2153C - Symmetrical Polygons](/contest/2153/problem/C "Codeforces Round 1057 (Div. 2)")
    168 
    169 **Hint 1**
    170 
    171 Consider the line of symmetry. It intersects with the polygon at no more than $2$ sticks if we don't consider the endpoints of the sides.
    172 
    173 **Hint 2**
    174 
    175 Other sticks come in pairs.
    176 
    177 **Solution**
    178 
    179 Any line intersects with the polygon at no more than $2$ sticks (Here, we don't consider the endpoints of the sides when talking about intersection).
    180 
    181 Consider the line of symmetry. The sticks not intersecting with it come in pairs of the same length.
    182 
    183 Once we group the sticks in pairs of the same length (some sticks are not grouped), we should always use all of the pairs to construct the symmetrical convex polygon.
    184 
    185 That is because, if we do not use all the pairs, for each unchosen pair, we can always add a copy of the stick on each side of the line of symmetry, which enlarges the perimeter. And if there exists a pair which we only use one of them as a side, it has to intersects with the line of symmetry. We can replace it with the pair on both sides of the line of symmetry and make the polygon convex with a larger perimeter.
    186 
    187 **Case 1:** The line of symmetry intersects none of the sticks.
    188 
    189 Only pairs of sticks with same length can be used. To obtain the largest perimeter, it is the most optimal to use all possible pairs.
    190 
    191 **Case 2:** The line of symmetry intersects exactly one stick.
    192 
    193 Let us call the stick that intersects the line of symmetry the *odd* stick. As long as the length of the odd stick is less than the total length of the pairs of sticks with identical length, we can use the odd stick. Hence, we can iterate through all possible sticks and check whether it is possible for it to be the odd stick in $O(1)$ time for each odd stick.
    194 
    195 **Case 3:** The line of symmetry intersects exactly two sticks.
    196 
    197 Let the longer of the two sticks that intersect the line of symmetry be the *long odd* stick, and the shorter be the *short odd* stick. As long as the difference in the length of the long odd stick and even odd stick is less than the total length of the pairs of sticks with identical length, we can use the long odd stick and short odd stick.
    198 
    199 Let's say the remaining sticks in ascending order are $v_1,v_2,\ldots,v_k\ (v_1\lt v_2\lt\ldots\lt v_k)$. If the longer stick we choose is $v_i\ (i\gt 1)$, then the shorter one we choose should always be $v_{i-1}$, because it is the longest one we can choose and the difference of the two sticks chosen is minimized.
    200 
    201 So you just need to check these pairs: $(v_1,v_2),(v_2,v_3),\ldots,(v_{k-1},v_k)$.
    202 
    203 The time complexity is $\mathcal{O}(n\log n)$.
    204 
    205 **Code (C++, maomao90)**
    206 
    207 ```
    208 #include <bits/stdc++.h>
    209 using namespace std;
    210  
    211 using ll = long long;
    212  
    213 const int MAXN = 200'005;
    214  
    215 int t;
    216 int n;
    217 int a[MAXN];
    218 map<int, int> cnt;
    219  
    220 int main() {
    221     ios::sync_with_stdio(0), cin.tie(0);
    222     cin >> t;
    223     while (t--) {
    224         cnt.clear();
    225  
    226         cin >> n;
    227         for (int i = 0; i < n; i++) {
    228             cin >> a[i];
    229         }
    230         for (int i = 0; i < n; i++) {
    231             cnt[a[i]]++;
    232         }
    233  
    234         ll base = 0;
    235         vector<int> odd, even;
    236         for (auto [x, c] : cnt) {
    237             base += (ll)x * (c / 2);
    238             if (c % 2 == 1) {
    239                 odd.push_back(x);
    240             } else if (c >= 2) {
    241                 even.push_back(x);
    242             }
    243         }
    244  
    245         if (base == 0) {
    246             cout << 0 << '\n';
    247             continue;
    248         }
    249  
    250         ll ans = 0;
    251         for (int x : odd) {
    252             if (2 * base > x) {
    253                 ans = max(ans, 2 * base + x);
    254             }
    255         }
    256  
    257         assert(is_sorted(odd.begin(), odd.end()));
    258         for (int i = 1; i < (int)odd.size(); i++) {
    259             if (odd[i - 1] + 2 * base > odd[i]) {
    260                 ans = max(ans, odd[i - 1] + 2 * base + odd[i]);
    261             }
    262         }
    263  
    264         for (int x : even) {
    265             if (base - x > 0) {
    266                 ans = max(ans, 2 * base);
    267             }
    268         }
    269  
    270         cout << ans << '\n';
    271     }
    272     return 0;
    273 }
    274 ```
    275 
    276 **Code (Pypy3.10, Little_Sheep_Yawn)**
    277 
    278 ```
    279 import sys
    280 input = lambda: sys.stdin.readline().strip()
    281 
    282 t = int(input())
    283 outs = []
    284  
    285 # avoiding hash collisions, which we don't have tests in the pretests
    286 rnd = random.getrandbits(30)
    287 fmax = lambda x, y: x if x > y else y
    288  
    289 for _ in range(t):
    290     n = int(input())
    291     nums = list(map(int, input().split()))
    292     
    293     cnt = Counter(x ^ rnd for x in nums)
    294     
    295     c = 0
    296     half = 0
    297     tmp = []
    298     
    299     for x in cnt:
    300         if cnt[x] > 1:
    301             c += cnt[x] // 2
    302             half += cnt[x] // 2 * (x ^ rnd)
    303         if cnt[x] % 2:
    304             tmp.append(x ^ rnd)
    305     
    306     tmp.sort()
    307     
    308     ans = 0 if c <= 1 else half * 2
    309     
    310     for x in tmp:
    311         if half * 2 > x:
    312             ans = fmax(ans, half * 2 + x)
    313     
    314     for i in range(1, len(tmp)):
    315         if half * 2 > tmp[i] - tmp[i - 1]:
    316             ans = fmax(ans, half * 2 + tmp[i - 1] + tmp[i])
    317     
    318     outs.append(ans)
    319  
    320 print('\n'.join(map(str, outs)))
    321 ```
    322 
    323 ### [2153D - Not Alone](/contest/2153/problem/D "Codeforces Round 1057 (Div. 2)")
    324 
    325 **Hint 1**
    326 
    327 Break up a nice array into "blocks" of same values.
    328 
    329 **Hint 2**
    330 
    331 Each block can be considered as blocks of size $2$ and $3$ concatenating together.
    332 
    333 **Solution**
    334 
    335 We can divide the nice circular array in blocks, where each block consists of equal values.
    336 
    337 The final circular array can be divided into blocks with size of at least $2$.
    338 
    339 And, since $2=2,3=3,4=2+2$, each block can be divided into sub-blocks of size $2$ and $3$:
    340 
    341 * If the block is of size $3k-1\ (k\gt 0)$, then $3k-1=1\cdot 2+(k-1)\cdot 3$.
    342 * If the block is of size $3k\ (k\gt 0)$, then $3k=0\cdot 2+k\cdot 3$.
    343 * If the block is of size $3k+1\ (k\gt 0)$, then $3k+1=2\cdot 2+(k-1)\cdot 3$.
    344 
    345 With this observation, we can modify the condition of a nice circular array as follows:
    346 
    347 > A circular array is nice if we can split it into contiguous blocks of length 2 or length 3, such that each block has equal value, and each element belongs to exactly one block.
    348 
    349 Let us first try to solve the easier problem where the array is not circular. Let $\text{dp}[i]$ be the minimum number of operations to make $[a_1,a_2,\ldots,a_i]$ nice. Then, by considering whether the last block containing $a_i$ is of length $2$ or length $3$, we can come up with the transition:
    350 
    351 $\text{dp}[i] = \min(\text{dp}[i - 2] + \text{cost}(a_{i - 1}, a_i), \text{dp}[i - 3] + \text{cost}(a_{i - 2}, a_{i - 1}, a_i))$
    352 
    353 where $\text{cost}$ denotes the minimum number of operations to make the elements equal.
    354 
    355 To solve the original problem where the array is circular, we can use the standard technique of splitting the circular array by cutting the circle between $(i, i + 1)$ for each $1\le i\le n$. This will take $\mathcal{O}(n^2)$ time. However, since the length of the blocks do not exceed $3$, we only need to try three splitting points $(1, 2)$, $(2, 3)$, and $(3, 4)$.
    356 
    357 The time complexity is $\mathcal{O}(n)$.
    358 
    359 **Code (C++, maomao90)**
    360 
    361 ```
    362 #include <bits/stdc++.h>
    363 using namespace std;
    364  
    365 using ll = long long;
    366  
    367 const ll LINF = 1000000000000000005;
    368 const int MAXN = 500005;
    369  
    370 int t;
    371 int n;
    372 int a[MAXN];
    373 ll dp[MAXN];
    374  
    375 ll cost(int x, int y) { return abs(x - y); }
    376  
    377 ll cost(int x, int y, int z) {
    378     if (x > y) {
    379         swap(x, y);
    380     }
    381     if (y > z) {
    382         swap(y, z);
    383     }
    384     if (x > y) {
    385         swap(x, y);
    386     }
    387     return z - x;
    388 }
    389  
    390 int main() {
    391     ios::sync_with_stdio(0), cin.tie(0);
    392     cin >> t;
    393     while (t--) {
    394         cin >> n;
    395         for (int i = 1; i <= n; i++) {
    396             cin >> a[i];
    397         }
    398  
    399         ll ans = LINF;
    400         for (int cyc = 0; cyc < 4; cyc++) {
    401             dp[0] = 0;
    402             dp[1] = LINF;
    403             for (int i = 2; i <= n; i++) {
    404                 dp[i] = dp[i - 2] + cost(a[i - 1], a[i]);
    405                 if (i >= 3) {
    406                     dp[i] =
    407                         min(dp[i], dp[i - 3] + cost(a[i - 2], a[i - 1], a[i]));
    408                 }
    409             }
    410             ans = min(ans, dp[n]);
    411  
    412             // cyclic shift anti-clockwise
    413             for (int i = 2; i <= n; i++) {
    414                 swap(a[i], a[i - 1]);
    415             }
    416         }
    417  
    418         cout << ans << '\n';
    419     }
    420     return 0;
    421 }
    422 ```
    423 
    424 **Code (Pypy3.10, Little_Sheep_Yawn)**
    425 
    426 ```
    427 import sys
    428 input = lambda: sys.stdin.readline().strip()
    429 
    430 t = int(input())
    431 outs = []
    432 fmin = lambda x, y: x if x < y else y
    433  
    434 inf = 10 ** 15
    435 for _ in range(t):
    436     n = int(input())
    437     nums = list(map(int, input().split()))
    438     
    439     ans = inf
    440     
    441     for _ in range(3):
    442         nums = nums[-1:] + nums[:-1]
    443         dp = [inf] * (n + 1)
    444         dp[0] = 0
    445         
    446         for i in range(2, n + 1):
    447             dp[i] = fmin(dp[i - 2] + max(nums[i-2:i]) - min(nums[i-2:i]),
    448                          dp[i - 3] + max(nums[i-3:i]) - min(nums[i-3:i]) if i >= 3 else inf)
    449         
    450         ans = fmin(ans, dp[n])
    451     
    452     outs.append(ans)
    453  
    454 print('\n'.join(map(str, outs)))
    455 ```
    456 
    457 ### [2153E - Zero Trailing Factorial](/contest/2153/problem/E "Codeforces Round 1057 (Div. 2)")
    458 
    459 **Hint 1**
    460 
    461 Why is the answer always smaller than $10^{100}$ ?
    462 
    463 **Hint 2**
    464 
    465 There are only a few $k$-s that are worth choosing.
    466 
    467 **Hint 3**
    468 
    469 $f_m(x, n)$ is equal to $0$ for a lot of the $x$.
    470 
    471 **Solution**
    472 
    473 Let $p_0$ be the largest prime that is not greater than $n$. Then, $f_m(x, n) = 0$ for all $x \lt p_0$.
    474 
    475 **Proof**
    476 
    477 $v_{p_0}(x!) = 0$ for all $x \lt p_0$, and $v_{p_0}(n!) \gt 0$. Hence, $w_{p_0}(x, n) = \min(v_{p_0}(x!), v_{p_0}(n!)) = 0$.
    478 
    479 Let $\mathrm{PrimeGap}(M)$ be the maximum difference between a number $x\ (2\leq x\leq M)$ and the largest prime number no larger than it. We only need to compute $\mathrm{PrimeGap}(n) \le \mathrm{PrimeGap}(10^7) = 152$ values of $f_m(x, n)$. As this is reasonably small, we will now try to calculate the value of each $f_m(x, n)$ for all possible $x \ge p_0$.
    480 
    481 First, we state a simple but useful lemma: for all $k\ge 2$, $v_k(a!) \le v_k(b!)$ if $a\le b$.
    482 
    483 **Proof**
    484 
    485 $a!$ divides $b!$ if $a\le b$. Hence, if $k^i$ divides $a!$, it also divides $b!$.
    486 
    487 To find out some more about $w_k(a,b)$, let's factor $k$ as $k=p_1^{v_1}p_2^{v_2}\ldots p_t^{v_t}$ where $p_1,p_2,\ldots,p_t$ are disctinct primes and $v_1,v_2,\ldots,v_t$ are positive integers.
    488 
    489 Then, $w_k(a,b)\geq\min\limits_i w_{p_i^{v_i}}(a,b)$.
    490 
    491 **Proof**
    492 
    493 Without loss of generality, let $a\le b$. Consider the array $c=[v_{p_1^{v_1}}(a!),v_{p_2^{v_2}}(a!),\ldots,v_{p_t^{v_t}}(a!)]$, $d=[v_{p_1^{v_1}}(b!),v_{p_2^{v_2}}(b!),\ldots,v_{p_t^{v_t}}(b!)]$. Then $c_i\leq d_i$, for all $1\leq i\leq n$, since $v_{p_i^{v_i}}(a!)\leq v_{p_i^{v_i}}(b!)$ from the earlier lemma.
    494 
    495 By definition, $v_k(a!) = \min(c)$, $v_k(b!) = \min(d)$, and
    496 
    497 $w_k(a, b) = \begin{cases}10^{100} & \text{if } \min(c) = \min(d)\\ \min(c) &\text{otherwise}\end{cases}$
    498 
    499 (the second case is due to the lemma $v_k(a!)\le v_k(b!)$).
    500 
    501 * If $v_k(a!) = v_k(b!)$, then $w_k(a,b)=10^{100}$. The inequality already holds.
    502 * Otherwise, $v_k(a!) \neq v_k(b!)$, i.e., $\min(c)\neq\min(d)$. Since $c_i\leq d_i$ for all $i$, $\min(c) \lt \min(d)$. Let $i'$ be the index such that $c_i' = \min(c)$. Then, $c_{i'} = \min(c) \lt \min(d) \le d_{i'}$. Hence, $w_{p_{i'}^{v_i'}}(a, b) = c_{i'} = w_k(a, b)$.
    503 
    504 Since $f_m(a, b)$ considers the minimum of $w_k(a, b)$ over all $2\le k\le m$, we only need to consider $k$ that are primes, or powers of primes. Formally, we only need to consider integers of the form $p^v$ where $p$ is a prime number and $v$ is a positive integer.
    505 
    506 Furthermore, we only need to consider numbers of the form $p^v$ where $p$ is a prime number and $p$ divides at least one of the numbers in $[p_0, n]$.
    507 
    508 **Proof**
    509 
    510 For each $x$ in $[p_0,n]$, $x!=(p_0-1)!p_0(p_0+1)\ldots x$, which means $v_p(x!)=v_p((p_0-1)!)$. So it always holds that $v_p(x!)=v_p(n!)$, which also implies that $v_{p^k}(x!)=v_{p^k}(n!)$.
    511 
    512 There are $\mathcal{O}(\mathrm{PrimeGap}(n)\log_2 n)$ primes $p$ that divide at least one of the numbers in $[p_0, n]$. We can calculate the value of $v_p(x!)$ and $v_p(n!)$ in $\mathcal{O}(\log_2 n)$ using the given formula. For each prime $p$, there are at most $\mathcal{O}(\log_2 m)$ prime powers $p^v \le m$, and $v_{p^k}(x!)$ and $v_{p^k}(n!)$ can both be calculated in $\mathcal{O}(1)$ time after computing $v_p(x!)$ and $v_p(n!)$ in the previous step. Hence, a single $f_m(x, n)$ can be computed in $\mathcal{O}(\mathrm{PrimeGap}(n)\log_2 n(\log_2 n + \log_2 m))$ time.
    513 
    514 The total time complexity if $\mathcal{O}(t\cdot \mathrm{PrimeGap}(n)^2\log_2 n(\log_2 n + \log_2 m))$. Even though this seems very big, the constant is very small, so it passess comfortably.
    515 
    516 **Code (C++, maomao90)**
    517 
    518 ```
    519 #include <bits/stdc++.h>
    520 using namespace std;
    521  
    522 using ll = long long;
    523  
    524 const int MAXN = 10000005;
    525 const int INF = 1000000005;
    526  
    527 bool is_prime[MAXN];
    528  
    529 inline int calc_v(int p, int x) {
    530     int res = 0;
    531     ll pw_p = p;
    532     while (pw_p <= x) {
    533         res += x / pw_p;
    534         pw_p *= p;
    535     }
    536     return res;
    537 }
    538  
    539 int t;
    540 int n, m;
    541 vector<int> small_primes;
    542  
    543 int main() {
    544 #ifndef DEBUG
    545     ios::sync_with_stdio(0), cin.tie(0);
    546 #endif
    547     for (int i = 2; i < MAXN; i++) {
    548         is_prime[i] = true;
    549     }
    550     for (int p = 2; (ll)p * p < MAXN; p++) {
    551         if (!is_prime[p]) {
    552             continue;
    553         }
    554         small_primes.push_back(p);
    555         for (int i = p * p; i < MAXN; i += p) {
    556             is_prime[i] = false;
    557         }
    558     }
    559  
    560     cin >> t;
    561     while (t--) {
    562         cin >> n >> m;
    563  
    564         // find largest prime q <= n. Requires at most 142 iterations (due to
    565         // prime gap)
    566         int q = n;
    567         while (!is_prime[q]) {
    568             q--;
    569         }
    570  
    571         // precompute the useful big primes
    572         vector<int> useful_p;
    573         for (int f = 1; (ll)f * f <= n; f++) {
    574             // p_bnd is the largest possible value such that floor(n / p_bnd) =
    575             // f n / p_bnd >= f p_bnd <= n / f
    576             int p_bnd = n / f;
    577             int p = p_bnd;
    578             while (!is_prime[p]) {
    579                 p--;
    580             }
    581             useful_p.push_back(p);
    582         }
    583  
    584         ll ans = 0;
    585         // for all x < q, f_m(x, n) = 0. try all x >= q
    586         for (int x = q; x < n; x++) {
    587             int res = INF;
    588  
    589             for (int p : useful_p) {
    590                 int vx = calc_v(p, x), vn = calc_v(p, n);
    591                 if (vx != vn) {
    592                     res = min(res, vx);
    593                 }
    594             }
    595  
    596             for (int p : small_primes) {
    597                 if ((ll)p * p > m) {
    598                     break;
    599                 }
    600  
    601                 int base_vx = calc_v(p, x), base_vn = calc_v(p, n);
    602                 for (ll exp = 1, pw_p = p; pw_p <= m; exp++, pw_p *= p) {
    603                     int vx = base_vx / exp, vn = base_vn / exp;
    604                     if (vx != vn) {
    605                         res = min(res, vx);
    606                     }
    607                 }
    608             }
    609  
    610             ans += res;
    611         }
    612  
    613         cout << ans << '\n';
    614     }
    615     return 0;
    616 }
    617 ```
    618 
    619 **Code (Pypy3.10, Little_Sheep_Yawn)**
    620 
    621 ```
    622 import sys
    623 input = lambda: sys.stdin.readline().strip()
    624 
    625 M = 10 ** 7
    626 pr = [1] * (M + 1)
    627  
    628 for i in range(2, M + 1):
    629     if pr[i] == 1:
    630         for j in range(i, M + 1, i):
    631             pr[j] = i
    632 
    633 t = int(input())
    634 outs = []
    635 
    636 fmin = lambda x, y: x if x < y else y
    637  
    638 inf = 10 ** 9
    639  
    640 for _ in range(t):
    641     n, m = map(int(input().split()))
    642     
    643     vis = set()
    644     
    645     for i in range(n, 0, -1):
    646         x = i
    647         while x > 1:
    648             vis.add(pr[x])
    649             x //= pr[x]
    650         
    651         if pr[i] == i: break
    652     
    653     ans = 0
    654     
    655     def f(val, p):
    656         c = 0
    657         while val:
    658             val //= p
    659             c += val
    660         return c
    661     
    662     for i in range(n - 1, 0, -1):
    663         res = inf
    664         
    665         for v in vis:
    666             cur = v
    667             c = 1
    668             
    669             v1 = f(i, v)
    670             v2 = f(n, v)
    671             
    672             while cur <= m:
    673                 
    674                 if v1 // c != v2 // c:
    675                     res = fmin(res, v1 // c)
    676                 
    677                 cur *= v
    678                 c += 1
    679         
    680         ans += res
    681         
    682         if pr[i] == i: break
    683     
    684     outs.append(ans)
    685  
    686 print('\n'.join(map(str, outs)))
    687 ```
    688 
    689 ### [2153F - Odd Queries on Odd Array](/contest/2153/problem/F "Codeforces Round 1057 (Div. 2)")
    690 
    691 **Hint 1**
    692 
    693 What does the condition "there do not exist four indices $1\leq i\lt j\lt k\lt l\leq m$ such that $b_i\neq b_j$, $b_i=b_k$ and $b_j=b_l$." reminds you of?
    694 
    695 **Hint 2**
    696 
    697 You can construct a tree based on the array. How can you do so?
    698 
    699 **Solution**
    700 
    701 The strange condition given by the problem is that there are no subsequences in the form of $[x,y,x,y]\ (x\neq y)$.
    702 
    703 Let us construct a tree such that its DFS order $^\dagger$ is equal to $a$. We can build the tree as follows:
    704 
    705 * Initialize a stack containing a vertex $0$.
    706 * Iterate over the array $a$ from index $i = 1$ to $i = n$.
    707 * For each element $a[i]$:
    708   + Add an edge between the vertex on top of the stack and vertex $i$. Assign vertex $i$ the value $a[i]$.
    709   + If this is the first occurrence of $a[i]$, push $i$ onto the stack.
    710   + If this is the last occurrence of $a[i]$, pop the top element from the stack (even if you have just pushed it).
    711 
    712 Only the first and last occurrence of each value affects the stack. It can be proven that at the last occurence of each value, the vertex being popped from the stack will have the same value as the value of the processed vertex. This is because all elements in between the first and last occurrence of a value $x$ must be strictly contained in the range (due to the property of a cute array). Hence, all vertices that are pushed into the stack after the first occurrence of $x$ will be popped out before the last occurrence of $x$.
    713 
    714 Due to the property of a cute array, the set of vertices with equal values forms a single connected component in the tre
    715 
    716 **Proof**
    717 
    718 Suppose that the set of vertices with equal values do not form a single connected component. Let $k$ be the value that do not form a single connected component, and let $u$ be the first occurrence of $a[u] = k$. Let $v$ be a vertex that is not connected to $u$, i.e., there exists a vertex $w$ on the simple path between $u$ and $v$ such that $a[w] \neq a[u]$.
    719 
    720 Vertex $u$ has to be an ancestor of vertex $v$. This is because vertex $u$ will be pushed into the stack, and will remain in the stack until the last occurrence of $a[u]$, so $u$ will still be in the stack when $v$ is being processed.
    721 
    722 Let $w$ be a vertex on the simple path between $u$ and $v$ such that $a[w] \neq a[u]$. $w$ is also an ancestor of $v$ since $u$ is an ancestor of $v$. $w$ has to be the first occurrence of $a[w]$ (for it to be pushed into the stack), and the last occurrence of $a[w]$ has to be after $v$ (otherwise it would be popped from the stack before $v$). This means that $[a[u], a[w], a[v], a[w]]$ exists as a subsequence of array $a$, which contradicts the condition of a cute array as $a[u] = a[v]$.
    723 
    724 Since there can only be one vertex in the stack for each value, all vertices of the same value have the same parent.
    725 
    726 To answer the queries, we decompose the range $l$ to $r$ into three parts by considering the lowest common ancestor (LCA) of vertex $l$ and vertex $r$:
    727 
    728 * From $l$ to LCA:
    729   + If $l$ has the same value as LCA, you can leave it to the second part.
    730   + Otherwise, let $l'$ be the child vertex of LCA which is an ancestor of $l$, and $\text{last}_{l'}$ be the vertex with the largest index in the subtree of $l'$. The values that appear in the subtree of $l'$ never occur in other parts of the tree. Hence, the answer for the subarray $a_{l\ldots \text{last}_{l'}}$ is equals to the answer for the suffix $a_{l\ldots n}$ minus the answer for the suffix $a_{\text{last}_{l'} + 1\ldots n}$. By precomputing the answer for each suffix of the entire array $a$, we can find the answer for subarray $a_{l\ldots \text{last}_{l'}}$ in $\mathcal{O}(1)$ time.
    731 * At LCA:
    732   + Let $r'$ be the child vertex of the LCA which is an ancestor of $r$. We want to compute the answer for the subarray $a_{\text{last}_{l'} + 1\ldots r'-1}$.
    733   + This can be done by considering the children of the LCA between $l'$ and $r'$, then summing up the answer for the subtrees of those children.
    734     - For subtrees that are a single vertex, they have the same value as the LCA. We can count the occurrence of the value between vertex $l'$ and $r'$ in $\mathcal{O}(1)$ time after precomputing prefix sums.
    735     - For other subtrees, the answer for their corresponding subarray is independent of the rest of the array. Hence, we can precompute the answer for the subtree of each vertex with a simple DFS. Then, we can sum up the answer for the subtrees of all children between $l'$ and $r'$ using perfix sums.
    736 * From LCA to $r$:
    737   + This is handled in the same way as the first part, except that we need to precompute the answer for each prefix of the entire array instead of the suffix.
    738 
    739 The time complexity is $\mathcal{O}(n+q\log n)$.
    740 
    741 $^\dagger$ The DFS order of a tree is found by calling the following `dfs` function on the tree.
    742 
    743 ```
    744 dfs_order = []
    745 
    746 def dfs(v):
    747 	dfs_order.append(v)
    748 	# children[v] is the set of children of vertex v
    749 	for child in children[v]:
    750 		dfs(child)
    751 
    752 dfs(0)
    753 ```
    754 
    755 **Code (Pypy 3.10, Little_Sheep_Yawn)**
    756 
    757 ```
    758 import sys
    759 import bisect
    760 input = lambda: sys.stdin.readline().strip()
    761 
    762 t = int(input())
    763 outs = []
    764 
    765 fmax = lambda x, y: x if x > y else y
    766  
    767 for _ in range(t):
    768     n, q = map(int, input().split())
    769     nums = [0] + list(map(int, input().split()))
    770     
    771     first_pos = [0] * (n + 1)
    772     last_pos = [0] * (n + 1)
    773     
    774     for i in range(n + 1):
    775         last_pos[nums[i]] = i
    776     
    777     for i in range(n, -1, -1):
    778         first_pos[nums[i]] = i
    779     
    780     path = [[] for _ in range(n + 1)]
    781     nth_parent = [[-1] * (n + 1) for _ in range(20)]
    782     depth = [0] * (n + 1)
    783     
    784     stk = [0]
    785     
    786     for i in range(1, n + 1):
    787         path[stk[-1]].append(i)
    788         nth_parent[0][i] = stk[-1]
    789         depth[i] = depth[stk[-1]] + 1
    790         
    791         if first_pos[nums[i]] == i:
    792             stk.append(i)
    793         if last_pos[nums[i]] == i:
    794             stk.pop()
    795     
    796     depth.append(-1)
    797     
    798     for i in range(19):
    799         for j in range(n + 1):
    800             if nth_parent[i][j] != -1:
    801                 nth_parent[i + 1][j] = nth_parent[i][nth_parent[i][j]]
    802     
    803     cnt = [0] * (n + 1)
    804     cur = 0
    805     
    806     pref_val = [0] * (n + 1)
    807     
    808     for i in range(1, n + 1):
    809         cur += -nums[i] if cnt[nums[i]] else nums[i]
    810         cnt[nums[i]] ^= 1
    811         pref_val[i] = cur
    812     
    813     cnt = [0] * (n + 1)
    814     cur = 0
    815  
    816     suff_val = [0] * (n + 1)
    817     
    818     for i in range(n, 0, -1):
    819         cur += -nums[i] if cnt[nums[i]] else nums[i]
    820         cnt[nums[i]] ^= 1
    821         suff_val[i - 1] = cur
    822  
    823     subtree_val = [0] * (n + 1)
    824     subtree_max_idx = list(range(n + 1))
    825     
    826     for i in range(n, -1, -1):
    827         if first_pos[nums[i]] == i:
    828             c = 1
    829             total = 0
    830             
    831             for j in path[i]:
    832                 total += subtree_val[j]
    833                 if nums[j] == nums[i]:
    834                     c ^= 1
    835                 subtree_max_idx[i] = fmax(subtree_max_idx[i], subtree_max_idx[j])
    836             
    837             subtree_val[i] = total + c * nums[i]
    838     
    839     accs = [[0] * (len(path[i]) + 2) if first_pos[nums[i]] == i else [] for i in range(n + 1)]
    840     
    841     for i in range(n + 1):
    842         if first_pos[nums[i]] == i:
    843             total = 0
    844             c = 1
    845             accs[i][1] = total * 2 + c
    846             
    847             for j in range(len(path[i])):
    848                 total += subtree_val[path[i][j]]
    849                 if nums[path[i][j]] == nums[i]:
    850                     c ^= 1
    851                 accs[i][j + 2] = total * 2 + c
    852     
    853     def lca(u, v):
    854         if depth[u] < depth[v]:
    855             u, v = v, u
    856         d = depth[u] - depth[v]
    857         
    858         while d:
    859             x = d & -d
    860             bit = x.bit_length() - 1
    861             u = nth_parent[bit][u]
    862             d -= x
    863         
    864         if u == v: return u
    865         
    866         for i in range(19, -1, -1):
    867             if nth_parent[i][u] != nth_parent[i][v]:
    868                 u = nth_parent[i][u]
    869                 v = nth_parent[i][v]
    870  
    871         return nth_parent[0][u]
    872     
    873     last = 0
    874     ans = [0] * q
    875     
    876     for idx in range(q):
    877         l, r = map(int, input().split())
    878         l = (l + last - 1) % n + 1
    879         r = (r + last - 1) % n + 1
    880         
    881         if l > r: l, r = r, l
    882         ancestor = lca(l, r)
    883  
    884         if l == r:
    885             last = nums[l]
    886         else:
    887             last = 0
    888             
    889             if l == ancestor and first_pos[nums[l]] == l:
    890                 pl = 0
    891             elif nth_parent[0][l] == ancestor and first_pos[nums[ancestor]] == ancestor and first_pos[nums[l]] != l:
    892                 pl = bisect.bisect_left(path[ancestor], l) + 1
    893             else:
    894                 cl = l
    895                 for i in range(19, -1, -1):
    896                     if depth[nth_parent[i][cl]] > depth[ancestor]:
    897                         cl = nth_parent[i][cl]
    898                 last += suff_val[l - 1] - suff_val[subtree_max_idx[cl]]
    899                 pl = bisect.bisect_left(path[ancestor], cl) + 2
    900             
    901             if r == ancestor and first_pos[nums[r]] == r:
    902                 pr = 0
    903             elif nth_parent[0][r] == ancestor and first_pos[nums[ancestor]] == ancestor and first_pos[nums[r]] != r:
    904                 pr = bisect.bisect_left(path[ancestor], r) + 1
    905             else:
    906                 cr = r
    907                 for i in range(19, -1, -1):
    908                     if depth[nth_parent[i][cr]] > depth[ancestor]:
    909                         cr = nth_parent[i][cr]
    910                 last += pref_val[r] - pref_val[cr - 1]
    911                 pr = bisect.bisect_left(path[ancestor], cr)
    912  
    913             xl = accs[ancestor][pl]
    914             xr = accs[ancestor][pr + 1]
    915             
    916             vl, cl = divmod(xl, 2)
    917             vr, cr = divmod(xr, 2)
    918             
    919             last += vr - vl + (cl ^ cr) * nums[ancestor]
    920  
    921         ans[idx] = last
    922     
    923     outs.append(' '.join(map(str, ans)))
    924  
    925 print('\n'.join(outs))
    926 ```
    927 
    928 **Code (C++, maomao90, slightly different)**
    929 
    930 ```
    931 #include <bits/stdc++.h>
    932 using namespace std;
    933  
    934 using ll = long long;
    935  
    936 namespace solution {
    937  
    938 const int MAXL = 21;
    939 const int MAXN = 1000005;
    940  
    941 int n, q;
    942 int a[MAXN];
    943 vector<int> occ[MAXN];
    944 ll pfx[MAXN], sfx[MAXN];
    945 ll sm_pfx[MAXN], sm_sfx[MAXN];
    946  
    947 inline bool is_first_occ(int i) { return occ[a[i]][0] == i; }
    948 inline bool is_last_occ(int i) { return occ[a[i]].back() == i; }
    949 // returns minimum j >= p such that a[j] == x, or n + 1 if does not exist
    950 inline auto nxt_occ(int p, int x) {
    951     return lower_bound(occ[x].begin(), occ[x].end(), p);
    952 }
    953  
    954 int p[MAXL][MAXN];
    955 vector<int> adj[MAXN];
    956 inline void add_edge(int u, int v) {
    957     p[0][v] = u;
    958     adj[u].push_back(v);
    959 }
    960  
    961 int lvl[MAXN];
    962 void dfs(int u) {
    963     for (int l = 1; l < MAXL; l++) {
    964         p[l][u] = p[l - 1][p[l - 1][u]];
    965     }
    966     if (u) {
    967         sm_pfx[u] += pfx[u];
    968         auto ptr = nxt_occ(u + 1, a[u]);
    969         sm_sfx[u] += ptr == occ[a[u]].end() ? 0 : sfx[*ptr];
    970     }
    971     for (int v : adj[u]) {
    972         lvl[v] = lvl[u] + 1;
    973         sm_pfx[v] = sm_pfx[u];
    974         sm_sfx[v] = sm_sfx[u];
    975         dfs(v);
    976     }
    977 }
    978  
    979 tuple<int, int, int> get_lca(int a, int b) {
    980     bool swp = false;
    981     if (lvl[a] < lvl[b]) {
    982         swap(a, b);
    983         swp = true;
    984     }
    985     for (int l = MAXL - 1; l >= 0; l--) {
    986         if (lvl[p[l][a]] >= lvl[b]) {
    987             a = p[l][a];
    988         }
    989     }
    990     if (a == b) {
    991         return {a, -1, -1};
    992     }
    993     if (swp) {
    994         swap(a, b);
    995     }
    996     for (int l = MAXL - 1; l >= 0; l--) {
    997         if (p[l][a] != p[l][b]) {
    998             a = p[l][a];
    999             b = p[l][b];
   1000         }
   1001     }
   1002     return {p[0][a], a, b};
   1003 }
   1004  
   1005 ll solve_same_layer(int l, int r) {
   1006     assert(p[0][l] == p[0][r]);
   1007     ll res =
   1008         (pfx[r] -
   1009          ((nxt_occ(r + 1, a[l]) - occ[a[l]].begin()) % 2 == 1 ? a[l] : 0)) -
   1010         (pfx[l] -
   1011          ((nxt_occ(l, a[l]) - occ[a[l]].begin() + 1) % 2 == 1 ? a[l] : 0));
   1012     if ((nxt_occ(r + 1, a[l]) - nxt_occ(l, a[l])) % 2 == 1) {
   1013         res += a[l];
   1014     }
   1015     return res;
   1016 }
   1017  
   1018 void precompute() {
   1019     for (int i = 0; i <= n; i++) {
   1020         occ[i].clear();
   1021         adj[i].clear();
   1022         pfx[i] = sfx[i] = sm_pfx[i] = sm_sfx[i] = 0;
   1023     }
   1024     for (int i = 1; i <= n; i++) {
   1025         occ[a[i]].push_back(i);
   1026     }
   1027     vector<int> stk;
   1028     stk.push_back(0);
   1029     for (int i = 1; i <= n; i++) {
   1030         if (!is_first_occ(i)) {
   1031             assert(!stk.empty() && a[stk.back()] == a[i]);
   1032             stk.pop_back();
   1033         }
   1034         assert(!stk.empty());
   1035         add_edge(stk.back(), i);
   1036         if (!is_last_occ(i)) {
   1037             stk.push_back(i);
   1038         }
   1039     }
   1040  
   1041     for (int u = n; u >= 0; u--) {
   1042         {
   1043             ll prv = 0;
   1044             for (int i = 0; i < (int)adj[u].size(); i++) {
   1045                 int v = adj[u][i];
   1046                 auto ptr = nxt_occ(v, a[v]);
   1047                 pfx[v] =
   1048                     prv + ((ptr - occ[a[v]].begin() + 1) % 2 == 1 ? a[v] : 0);
   1049                 if (!adj[v].empty()) {
   1050                     prv += pfx[adj[v].back()];
   1051                 }
   1052                 if (is_last_occ(v)) {
   1053                     prv += occ[a[v]].size() % 2 == 1 ? a[v] : 0;
   1054                 }
   1055             }
   1056         }
   1057         {
   1058             ll prv = 0;
   1059             for (int i = (int)adj[u].size() - 1; i >= 0; i--) {
   1060                 int v = adj[u][i];
   1061                 auto ptr = nxt_occ(v, a[v]);
   1062                 if (!adj[v].empty()) {
   1063                     prv += sfx[adj[v][0]];
   1064                 }
   1065                 sfx[v] = prv + ((occ[a[v]].end() - ptr) % 2 == 1 ? a[v] : 0);
   1066                 if (is_first_occ(v)) {
   1067                     prv += occ[a[v]].size() % 2 == 1 ? a[v] : 0;
   1068                 }
   1069             }
   1070         }
   1071     }
   1072  
   1073     dfs(0);
   1074 }
   1075  
   1076 void init(int _n, int _q, vector<int> _a) {
   1077     n = _n;
   1078     q = _q;
   1079     for (int i = 1; i <= n; i++) {
   1080         a[i] = _a[i - 1];
   1081     }
   1082     precompute();
   1083 }
   1084  
   1085 ll query(int l, int r) {
   1086     if (l == r) {
   1087         return a[l];
   1088     }
   1089     auto [lca, lc, rc] = get_lca(l, r);
   1090     assert(lca != r);
   1091     if (lca == l) {
   1092         ll ans = sm_pfx[r] - sm_pfx[l] + a[l];
   1093         return ans;
   1094     } else if (lc == l) {
   1095         ll ans = sm_pfx[r] - sm_pfx[rc];
   1096         ans += solve_same_layer(l, rc);
   1097         return ans;
   1098     } else {
   1099         ll ans = sfx[l] + sm_sfx[p[0][l]] - sm_sfx[lc] + sm_pfx[r] - sm_pfx[rc];
   1100         ans += solve_same_layer(*nxt_occ(lc + 1, a[lc]), rc);
   1101         return ans;
   1102     }
   1103 }
   1104  
   1105 } // namespace solution
   1106  
   1107 int main() {
   1108     ios::sync_with_stdio(0), cin.tie(0);
   1109     int t;
   1110     cin >> t;
   1111     while (t--) {
   1112         int n, q;
   1113         cin >> n >> q;
   1114         vector<int> a(n);
   1115         for (int i = 0; i < n; i++) {
   1116             cin >> a[i];
   1117         }
   1118  
   1119         solution::init(n, q, a);
   1120         ll prv_ans = 0;
   1121         while (q--) {
   1122             int l, r;
   1123             cin >> l >> r;
   1124             auto decode = [&](int x) { return (x - 1 + prv_ans) % n + 1; };
   1125             l = decode(l);
   1126             r = decode(r);
   1127             if (l > r) {
   1128                 swap(l, r);
   1129             }
   1130             ll ans = solution::query(l, r);
   1131             cout << ans << ' ';
   1132             prv_ans = ans;
   1133         }
   1134         cout << '\n';
   1135     }
   1136     return 0;
   1137 }
   1138 ```