1780.md (25596B)
1 Source: https://codeforces.com/blog/entry/111841 2 3 [1780A - Hayato and School](/contest/1780/problem/A "Codeforces Round 846 (Div. 2)") 4 5 Idea: [AndreyPavlov](/profile/AndreyPavlov "Master AndreyPavlov") 6 Preparation: [AndreyPavlov](/profile/AndreyPavlov "Master AndreyPavlov") 7 Editorialist: [AndreyPavlov](/profile/AndreyPavlov "Master AndreyPavlov") 8 9 **Tutorial** 10 11 Note that there are two variants of which numbers to take to make their amount odd: $3$ odd number; $2$ even and $1$ odd. Let’s save all indices of even and odd numbers into two arrays, and check both cases. 12 13 **Implementation (Python)** 14 15 ``` 16 def solve(): 17 n = int(input()) 18 a = list(map(int, input().split())) 19 odd, even = [], [] 20 for i in range(n): 21 if a[i] % 2 == 0: 22 even.append(i + 1) 23 else: 24 odd.append(i + 1) 25 if len(odd) >= 1 and len(even) >= 2: 26 print("YES") 27 print(odd[0], even[0], even[1]) 28 elif len(odd) >= 3: 29 print("YES") 30 print(odd[0], odd[1], odd[2]) 31 else: 32 print("NO") 33 34 t = int(input()) 35 for test in range(t): 36 solve() 37 ``` 38 39 **Implementation (C++)** 40 41 ``` 42 #include <bits/stdc++.h> 43 44 using namespace std; 45 46 int main() { 47 int T; 48 cin >> T; 49 while (T--) { 50 int n; 51 cin >> n; 52 vector<int> odd, even; 53 for (int i = 1; i <= n; i++) { 54 int x; 55 cin >> x; 56 if (x % 2 == 0) { 57 even.push_back(i); 58 } else { 59 odd.push_back(i); 60 } 61 } 62 if (odd.size() >= 3) { 63 cout << "YES\n"; 64 cout << odd[0] << " " << odd[1] << " " << odd[2] << '\n'; 65 } else if (odd.size() >= 1 && even.size() >= 2) { 66 cout << "YES\n"; 67 cout << odd[0] << " " << even[0] << " " << even[1] << '\n'; 68 } else { 69 cout << "NO\n"; 70 } 71 } 72 } 73 ``` 74 75 [1780B - GCD Partition](/contest/1780/problem/B "Codeforces Round 846 (Div. 2)") 76 77 Idea: [74TrAkToR](/profile/74TrAkToR "International Master 74TrAkToR") 78 Preparation: [qualdoom](/profile/qualdoom "Master qualdoom") 79 Editorialist: [qualdoom](/profile/qualdoom "Master qualdoom") 80 81 **Tutorial** 82 83 Let's note that it doesn't make sense for us to divide into more than $k = 2$ subsegments. Let's prove it. 84 85 Let us somehow split the array $a$ into $m \gt 2$ subsegments : $b_1, b_2, \ldots, b_m$. Note that $\gcd(b_1, b_2, \ldots, b_m) \le \gcd(b_1 + b_2, b_3, \ldots, b_m)$, since if $b_1$ and $b_2$ were multiples of $\gcd(b_1, b_2 , \ldots, b_m)$, so $b_1 + b_2$ is also a multiple of $\gcd(b_1, b_2, \ldots, b_m)$. This means that we can use $b_1 + b_2$ instead of $b_1$ and $b_2$, and the answer will not worsen, thus it is always beneficial to use no more than $k = 2$ subsegments. 86 87 How to find the answer? Let $s$ be the sum of the array $a$. Let's say $pref_i = {\sum_{j = 1}^{i} a_j}$, then the answer is $\max\limits_{1 \le i \lt n}(\gcd(pref_i, s - pref_i)$. 88 89 **Implementation (Python)** 90 91 ``` 92 from math import gcd 93 t = int(input()) 94 for test in range(t): 95 n = int(input()) 96 a = list(map(int, input().split())) 97 s = 0 98 for i in range(n): 99 s += a[i] 100 ans = 0 101 pref = 0 102 for i in range(n - 1): 103 pref += a[i] 104 ans = max(ans, gcd(pref, s - pref)) 105 print(ans) 106 ``` 107 108 **Implementation (С++)** 109 110 ``` 111 #include <bits/stdc++.h> 112 using namespace std; 113 int main() { 114 ios::sync_with_stdio(false); 115 cin.tie(0), cout.tie(0); 116 int T = 1; 117 cin >> T; 118 while (T--) { 119 int n; 120 cin >> n; 121 vector<int> a(n); 122 for (int i = 0; i < n; i++) cin >> a[i]; 123 long long s = accumulate(a.begin(), a.end(), 0ll), cur = 0; 124 long long ans = 1; 125 for (int i = 0; i < n - 1; i++) { 126 cur += a[i], s -= a[i]; 127 ans = max(ans, __gcd(s, cur)); 128 } 129 cout << ans << "\n"; 130 } 131 } 132 ``` 133 134 [1780D - Bit Guessing Game](/contest/1780/problem/D "Codeforces Round 846 (Div. 2)") 135 136 Idea: [AndreyPavlov](/profile/AndreyPavlov "Master AndreyPavlov") 137 Preparation: [qualdoom](/profile/qualdoom "Master qualdoom"), [AndreyPavlov](/profile/AndreyPavlov "Master AndreyPavlov") 138 Editorialist: [qualdoom](/profile/qualdoom "Master qualdoom"), [AndreyPavlov](/profile/AndreyPavlov "Master AndreyPavlov") 139 140 **Tutorial** 141 142 There are two similar solutions to this problem, we will tell you both. 143 144 **Tutorial (AndreyPavlov)** 145 146 Subtract $1$. What can we say now about the number of units at the beginning of the binary notation of a number? There are exactly $cnt - cnt_w + 1$, where $cnt$ is the number of unit bits after subtracting the unit, and $cnt_w$ is — before subtracting. Now we subtract them, for this we need to subtract the number $2^{cnt - cnt_w + 1} - 1$ and continue the algorithm. But such an algorithm makes at worst $60$ requests. To save queries, note that we know the number of units after we remove the units from the beginning, therefore it is useless to make another request for this. Then at the same time, as we remove the units from the beginning, we will immediately subtract the unit. As a result, there will be absolutely no more than $cnt$ operations, where $cnt$ is the initial number of single bits in the record of the number $n$. This number does not exceed $O(log_2(n))$, in turn, $log_2(n)$ does not exceed 30, which fits into the restrictions. 147 148 **Tutorial (qualdoom)** 149 150 Let $ans$ be the desired number $n$, and $was$ be the initial number of bits in the number $n$. Let's subtract the powers of two : $2^0, 2^1, 2^2, ... 2^ k$, while $was$ it will not become 0. We will support the $Shift$ flag — whether there was a bit transfer to $n$ when subtracting any power of two. Suppose we subtracted $2^k$ at the $k$th step and the number of bits became equal to $cnt_{new}$, and before the subtraction was $cnt$, then consider two cases. 151 152 1) $cnt - cnt_{new} = 1$, then bit $k$ was included in $n$ at the $k$th step, and if $Shift = false$, then we add to $ans$ — $2^k$, since there was no bit transfer, which means bit k is also in the original number, and subtract from $was$ — $1$. If $Shift = true$, then we added this bit during previous operations, and it does not need to be taken into account. 153 154 2) $cnt - cnt_{new} \neq 1$, then we know that the number of bits has not decreased, also that in the number $n$ there was such a bit $m$ that $2^m \gt 2^k$, and at the same time the bit $m$ is in $n$. Moreover, $m - k - 1 = cnt_{new} - cnt$. So $m = k + 1 + cnt_{new} - cnt$. Let's add $2^m$ to the answer, subtract from $was$ — $1$ and assign the $Shift$ flag the value $true$, since there was a bit transfer. 155 156 Thus, we found the initial number $n$, which is equal to $ans$, and also made no more than $O(log_2(n))$ queries, since $k\le log_2(n)$. 157 158 Thus, the solution spends no more than 30 requests, which fits into the limitations of the task. 159 160 **Implementation (Python)** 161 162 ``` 163 t = int(input()) 164 def ask (x): 165 print('-', x) 166 return int(input()) 167 for i in range(t): 168 cur = int(input()) 169 add = 0 170 ans = 0 171 while cur > 0: 172 x = ask(add + 1) 173 back = x - cur + 1 174 add = 2 ** back - 1 175 ans += 2 ** back 176 cur = x - back 177 print('!', ans) 178 ``` 179 180 **Implementation (С++)** 181 182 ``` 183 #include <iostream> 184 185 using namespace std; 186 187 int ask (int x) { 188 cout << "- " << x << endl; 189 if (x == -1) 190 exit(0); 191 cin >> x; 192 return x; 193 } 194 195 int main() { 196 int t; 197 cin >> t; 198 while (t--) { 199 int cnt; 200 cin >> cnt; 201 int n = 0; 202 int was = 0; 203 while (cnt > 0) { 204 n += 1; 205 int nw = ask(1 + was); 206 int back = nw - cnt + 1; 207 n += (1 << back) - 1; 208 was = (1 << back) - 1; 209 cnt = nw - back; 210 } 211 cout << "! " << n << endl; 212 } 213 } 214 ``` 215 216 [1780E - Josuke and Complete Graph](/contest/1780/problem/E "Codeforces Round 846 (Div. 2)") 217 218 Idea: [IzhitskiyTimofey](/profile/IzhitskiyTimofey "Master IzhitskiyTimofey") 219 Preparation: [IzhitskiyTimofey](/profile/IzhitskiyTimofey "Master IzhitskiyTimofey") 220 Editorialist: [IzhitskiyTimofey](/profile/IzhitskiyTimofey "Master IzhitskiyTimofey") 221 222 **Tutorial** 223 224 Let’s fix $g$ and check that the $g$ weight edge exists in $G'$. The first number, which is divided into $g$, starting with $L$ — $\lceil \frac{L}{g} \rceil \cdot g$, and the second — $(\lceil \frac{L}{g} \rceil + 1) \cdot g$, note that their $\gcd$ is $g$, so the edge between these vertices weighs $g$. If the second number is greater $R$, the edge with weight $g$ in the $G'$ doesn't exist, because on the segment from $L$ to $R$ at most one vertex, which is divided by $g$. That is, we should calculate the number of such $g$, which is $(\lceil \frac{L}{g} \rceil + 1) \cdot g \leq R$. 225 226 For $g \geq L$: $(\lceil \frac{L}{g} \rceil + 1) \cdot g = 2 \cdot g$. Get the upper limit on the $g \leq \lfloor \frac{R}{2} \rfloor$. That is, all $g$ on segment from $L$ to $\lfloor \frac{R}{2} \rfloor$ occur in the $G'$ as weight some edge. Add them to the answer. 227 228 Look at $g \lt L$. 229 230 Note that $\lceil \frac{L}{g} \rceil$ takes a $O(\sqrt{L})$ of different values. Let's fix some $f = \lceil \frac{L}{g} \rceil$. Note that $f$ corresponds to a consecutive segment $l \leq g \leq r$. Let's brute this segments in ascending order $f$. Then, if there is a left border $l$ of the segment, you can find $r$ either by binary search or by writing the formula. The next left border is $r + 1$. Then note, if $f$ is fixed, then $(f + 1) \cdot g \leq R$ is equivalent to $g \leq \lfloor \frac{R}{f + 1} \rfloor$. That is, with a fixed segment from $l$ to $r$, $g$ occurs in the $G'$ as weight some edge if $l \leq g \leq min(r, \lfloor \frac{R}{f + 1} \rfloor)$. Then brute all these segments and sum up of all good $g$. 231 232 Overall time complexity is $O(\sqrt{L})$ or $O(\sqrt{L} \cdot log(L))$. 233 234 **Implementation (Python)** 235 236 ``` 237 def solve(): 238 L, R = map(int, input().split()) 239 ans = max(0, R // 2 - L + 1) 240 left = 1 241 while left < L: 242 C = (L + left - 1) // left 243 right = (L + C - 2) // (C - 1) - 1 244 ans += max(0, min(right, R // (C + 1)) - left + 1) 245 left = right + 1 246 print(ans) 247 t = int(input()) 248 for test in range(t): 249 solve() 250 ``` 251 252 **Implementation (С++)** 253 254 ``` 255 #include <bits/stdc++.h> 256 using namespace std; 257 typedef long long ll; 258 int main(){ 259 ios::sync_with_stdio(false); 260 cin.tie(0), cout.tie(0); 261 int t; 262 cin >> t; 263 for (int test_case = 0; test_case < t; test_case++){ 264 ll L, R; 265 cin >> L >> R; 266 ll ans = max(0ll, R / 2 - L + 1); 267 for (ll left = 1, right; left < L; left = right + 1){ 268 ll C = (L + left - 1) / left; 269 right = (L + C - 2) / (C - 1) - 1; 270 ans += max(0ll, min(right, R / (C + 1)) - left + 1); 271 } 272 cout << ans << '\n'; 273 } 274 } 275 ``` 276 277 [1780F - Three Chairs](/contest/1780/problem/F "Codeforces Round 846 (Div. 2)") 278 279 Idea: [AndreyPavlov](/profile/AndreyPavlov "Master AndreyPavlov") 280 Preparation: [AndreyPavlov](/profile/AndreyPavlov "Master AndreyPavlov") 281 Editorialist: [qualdoom](/profile/qualdoom "Master qualdoom") 282 283 **Tutorial** 284 285 Let's sort the array and process the triples $i, j, k$, assuming that $i \lt j \lt k$ and $a_i \lt a_j \lt a_k$. Now if $\gcd(a_i, a_k) = 1$, then the number of ways to take the index $j$ is $k - i - 1$. 286 287 We will consider the answer to the problem for each $k$ from $1$ to $n$, assuming that $a_k$ is the maximum number in the triple. Now let $c$ be the number of numbers that are mutually prime with $a_k$ on the prefix from $1$ to $k - 1$, and $sum$ is the sum of their indices. Then you need to add $c\cdot i - sum - c$ to the answer. 288 289 It remains to find out the number of numbers that are mutually prime with $a_k$ and the sum of their indices. This can be done using the inclusion and exclusion method. Let $cnt_i$ be the number of numbers $a_j$ that are divisible by $i$, $s_i$ be the sum of the indices $j$ of numbers $a_j$ that are divisible by $i$. Let's look at the prime numbers $p_1, p_2, ..., p_m$ included in the factorization of the number $a_k$. 290 291 Then let $c$ initially be equal to the number of numbers on the prefix, and $sum$ to the sum of the indices on the prefix. Note that then we took into account the extra elements — numbers that are divisible by $p_1, p_2, ..., p_m$, since they will not be mutually simple with $a_k$, we subtract them from $c$ and $sum$. But having done this, we again took into account the extra elements that are multiples of the numbers of the form $p_i * p_j$, where $i \neq j$, add them back, etc. So we can iterate over the mask $mask$ of the primes $p_1, p_2, ..., p_m$. And depending on the parity of the bits in the mask, we will subtract or add elements that are multiples of $d$, where $d$ is the product of the primes included in $mask$. Having received $c$ and $sum$, we can recalculate the answer for the position $i$. 292 293 To move from position $i$ to position $i+1$, update the values of $cnt$ and $s$ by adding the element $a_{i-1}$ by iterating over the mask of the simple element $a_{i-1}$. 294 295 **Implementation (С++)** 296 297 ``` 298 #include "bits/stdc++.h" 299 300 using namespace std; 301 302 #include <ext/pb_ds/assoc_container.hpp> 303 using namespace __gnu_pbds; 304 305 #define sz(v) ((int)(v).size()) 306 #define all(a) (a).begin(), (a).end() 307 #define rall(a) a.rbegin(), a.rend() 308 #define F first 309 #define S second 310 #define pb push_back 311 #define ppb pop_back 312 #define eb emplace_back 313 #define time ((double)clock() / (double)CLOCKS_PER_SEC) 314 315 using pii = pair<int, int>; 316 using ll = long long; 317 using int64 = long long; 318 using ld = double; 319 320 const ll infll = (ll) 1e18 + 27; 321 const ll inf = (ll) 1e9; 322 323 #define dbg(x) cout << #x << " = " << (x) << endl 324 325 template<class T> 326 using pq = priority_queue<T, vector<T>, less<T>>; 327 template<class T> 328 using pqr = priority_queue<T, vector<T>, greater<T>>; 329 330 template<typename T, typename T2> 331 istream &operator>>(istream &in, pair<T, T2> &b) { 332 in >> b.first >> b.second; 333 return in; 334 } 335 336 template<typename T, typename T2> 337 ostream &operator<<(ostream &out, const pair<T, T2> &b) { 338 out << "{" << b.first << ", " << b.second << "}"; 339 return out; 340 } 341 342 template<typename T> 343 istream &operator>>(istream &in, vector<T> &b) { 344 for (auto &v : b) { 345 in >> v; 346 } 347 return in; 348 } 349 350 template<typename T> 351 ostream &operator<<(ostream &out, vector<T> &b) { 352 for (auto &v : b) { 353 out << v << ' '; 354 } 355 return out; 356 } 357 358 template<typename T> 359 ostream &operator<<(ostream &out, deque<T> &b) { 360 for (auto &v : b) { 361 out << v << ' '; 362 } 363 return out; 364 } 365 366 template<typename T> 367 void print(T x, string end = "\n") { 368 cout << x << end; 369 } 370 371 372 template<typename T1, typename T2> 373 bool chkmin(T1 &x, const T2 &y) { return x > y && (x = y, true); } 374 375 template<typename T1, typename T2> 376 bool chkmax(T1 &x, const T2 &y) { return x < y && (x = y, true); } 377 378 mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); 379 380 const int N = 3e5 + 10; 381 382 ll s[N]; 383 ll cnt[N]; 384 385 ll d[N][20]; 386 int ptr[N]; 387 bool u[N]; 388 389 ll Cnt = 0; 390 ll Sum = 0; 391 392 ll Ans = 0; 393 394 void Answer (int x, int pos) { 395 ll C = Cnt; 396 ll X = Sum; 397 int K = (1ll << ptr[x]); 398 for (int mask = 1; mask < K; mask++) { 399 ll k = 1; 400 for (int j = 0; j < ptr[x]; j++) { 401 if ((mask >> j) & 1) { 402 k *= d[x][j]; 403 } 404 } 405 int bits = __builtin_popcount(mask); 406 int D = k; 407 if (bits % 2 == 1) { 408 C -= cnt[D]; 409 X -= s[D]; 410 } else { 411 C += cnt[D]; 412 X += s[D]; 413 } 414 } 415 Ans += C * pos - X; 416 } 417 418 void add (int x, int pos) { 419 Cnt += 1; 420 Sum += pos + 1; 421 auto v = d[x]; 422 int K = (1ll << ptr[x]); 423 for (int mask = 1; mask < K; mask++) { 424 ll k = 1; 425 for (int j = 0; j < ptr[x]; j++) { 426 if ((mask >> j) & 1) { 427 k *= d[x][j]; 428 } 429 } 430 int D = k; 431 s[D] += pos + 1; 432 cnt[D] += 1; 433 } 434 } 435 436 void solve() { 437 for (int i = 2; i < N; i++) { 438 if (!u[i]) { 439 for (int j = i; j < N; j += i) { 440 u[j] = true; 441 d[j][ptr[j]] = i; 442 ptr[j]++; 443 } 444 } 445 } 446 int n; 447 cin >> n; 448 vector<int> a(n); 449 cin >> a; 450 sort(all(a)); 451 for (int i = 0; i < n; i++) { 452 Answer(a[i], i); 453 if (i > 0) { 454 add(a[i - 1], i - 1); 455 } 456 } 457 cout << Ans << "\n"; 458 } 459 460 int32_t main() { 461 ios::sync_with_stdio(false); 462 cin.tie(nullptr); 463 cout.tie(nullptr); 464 solve(); 465 return 0; 466 } 467 ``` 468 469 [1780G - Delicious Dessert](/contest/1780/problem/G "Codeforces Round 846 (Div. 2)") 470 471 Idea: [IzhitskiyTimofey](/profile/IzhitskiyTimofey "Master IzhitskiyTimofey") 472 Preparation: [IzhitskiyTimofey](/profile/IzhitskiyTimofey "Master IzhitskiyTimofey"), [AndreyPavlov](/profile/AndreyPavlov "Master AndreyPavlov") 473 Editorialist: [IzhitskiyTimofey](/profile/IzhitskiyTimofey "Master IzhitskiyTimofey"), [AndreyPavlov](/profile/AndreyPavlov "Master AndreyPavlov") 474 475 **Tutorial** 476 477 This problem has several solutions using different suffix structures. We will tell two of them — using suffix array, and using suffix automaton. 478 479 **Suffix array (t4m0fey)** 480 481 Let's build suffix array $suf$ and array $lcp$ (largest common prefixes) on the string $s$. Fix some $k \gt 1$ и consider about all substring $s$ length $k$. Match $1$ to positions $i$ array $lcp$, such that $lcp_i \geq k$, and match $0$ to other positions. One in position $i$ means that the substrings length $k$ starting at $suf_i$ and $suf_{i + 1}$ are equal. Consider any block of units length $len$, then for $len + 1$ substrings length $k$ number of occurrences in $s$ — $len + 1$, then in order for the substrings in this block to be delicious, it is necessary that $len + 1$ divided by $k$. 482 483 Let's brute $k$ from $n$ to $2$ и sustain all sizes blocks. Then, when shift to a new $k$ should events — change $0$ to $1$, for all $i$, such that $lcp_i = k$. To do this you can sustain DSU (Disjoint set union). Then for each block size we know the number of blocks with this size. Then it is enough to consider all blocks of length $len$, such as $len + 1$ — divider $k$. It can be done explicitly, just brute $k$, $2 \cdot k$, ..., as $len + 1$. And this works in sum of harmonic series: ${\sum_{k = 2}^{n} \lfloor \frac{n}{k} \rfloor}$ $= O(n \cdot log(n))$. 484 485 For $k = 1$, obviously, any substring length $1$ satisfies, so you can just add $n$ to the answer. 486 487 Overall time complexity is $O(n \cdot log(n))$. 488 489 **Suffix automaton (AndreyPavlov)** 490 491 The solution with the suffix automaton is as follows: let's build the suffix automaton itself, now we calculate for each vertex of the suffix automaton the dynamics $dp_v$ — this is the number of paths from the vertex $v$ to the terminal vertices. This dynamics means the number of occurrences of the substring corresponding to this vertex in the entire string. Let's introduce the function $f(v)$ — the length of the longest substring leading to the vertex $v$. We know that all substrings of length from $l_v$ to $r_v$ lead to the vertex $v$ of the suffix automaton — each once. Where $r_v = f(v)$ and $l_v = f(suff_v) + 1$, where $suff_v$ is the suffix link of $v$. Why is it so? All substrings of the form $s[x:k], s[x+1:k], ..., s[y:k]$ lead to the vertex $v$ of the suffix automaton, and there is a suffix link $suff_v$ to which lead all substrings of the form $s[x + 1:k], s[y + 2:k], ..., s[t: k]$. 492 493 In order to solve the problem, let's go through the $v$ vertex and look at the number of occurrences of any substring that leads to the $v$ — $dp_v$ vertex, then fix $c$ — the number of such $l_v \le x \le r_v$, that $dp_v$ is evenly divisible by $x$. Therefore, $dp_v \cdot c$ must be added to the answer. All divisors can be stored in $O(n \cdot log(n))$ and each time find the number of such $x$ by binsearch. 494 495 Asymptotics $O(n \cdot log(n))$ 496 497 **Implementation (t4m0fey)** 498 499 ``` 500 #include <bits/stdc++.h> 501 502 using namespace std; 503 504 typedef long long ll; 505 506 vector<int> suffix_array(string s){ 507 int n = s.size(); 508 vector<int> a(n), c(n), h(n); 509 vector<pair<char, int>> t; 510 for (int i = 0; i < n; i++) t.push_back({s[i], i}); 511 sort(t.begin(), t.end()); 512 int cur = -1; 513 for (int i = 0; i < n; i++){ 514 if (i == 0 || t[i].first != t[i - 1].first){ 515 cur++; 516 h[cur] = i; 517 } 518 a[i] = t[i].second; 519 c[a[i]] = cur; 520 } 521 vector<int> a1(n), c1(n); 522 for (int len = 1; len < n; len *= 2){ 523 for (int i = 0; i < n; i++){ 524 int j = (n + a[i] - len) % n; 525 a1[h[c[j]]++] = j; 526 } 527 a = a1; 528 cur = -1; 529 for (int i = 0; i < n; i++){ 530 if (i == 0 || c[a[i]] != c[a[i - 1]] || c[(a[i] + len) % n] != c[(a[i - 1] + len) % n]){ 531 cur++; 532 h[cur] = i; 533 } 534 c1[a[i]] = cur; 535 } 536 c = c1; 537 } 538 return a; 539 } 540 vector<int> build_lcp(string s, vector<int> suf){ 541 int n = s.size(); 542 vector<int> rsuf(n), lcp(n); 543 for (int i = 0; i < n; i++) rsuf[suf[i]] = i; 544 int cur = 0; 545 for (int i = 0; i < n; i++){ 546 int j = rsuf[i]; 547 if (j != n - 1){ 548 while (s[suf[j] + cur] == s[suf[j + 1] + cur]) cur++; 549 lcp[j] = cur; 550 } 551 if (cur > 0) cur--; 552 } 553 return lcp; 554 } 555 const int N = 1e6 + 1; 556 int r[N], l[N], us[N], cnt[N]; 557 vector<int> pos[N]; 558 559 int main() { 560 ios::sync_with_stdio(false), cin.tie(0); 561 int n; 562 cin >> n; 563 string s; 564 cin >> s; 565 s += '$'; 566 vector<int> suf = suffix_array(s); 567 vector<int> lcp = build_lcp(s, suf); 568 for (int i = 0; i < lcp.size(); i++) { 569 pos[lcp[i]].push_back(i); 570 } 571 ll ans = n; 572 for (int k = n; k >= 2; k--) { 573 for (int i : pos[k]) { 574 // add i 575 us[i] = true; 576 cnt[1]++; 577 l[i] = r[i] = i; 578 if (i != 0 && us[i - 1]) { 579 cnt[i - l[i - 1]]--; 580 cnt[1]--; 581 cnt[i - l[i - 1] + 1]++; 582 l[i] = l[i - 1]; 583 r[l[i - 1]] = i; 584 } 585 if (i + 1 < lcp.size() && us[i + 1]) { 586 cnt[r[i + 1] - i]--; 587 cnt[i - l[i] + 1]--; 588 cnt[r[i + 1] - l[i] + 1]++; 589 l[r[i + 1]] = l[i]; 590 r[l[i]] = r[i + 1]; 591 } 592 } 593 for (int x = k; x <= n; x += k) { 594 ans += 1ll * x * cnt[x - 1]; 595 } 596 } 597 cout << ans << "\n"; 598 } 599 ``` 600 601 **Implementation (AndreyPavlov)** 602 603 ``` 604 /* Includes */ 605 #include <bits/stdc++.h> 606 #include <ext/pb_ds/tree_policy.hpp> 607 608 /* Using libraries */ 609 using namespace std; 610 611 /* Defines */ 612 #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) 613 #define ld long double 614 #define pb push_back 615 #define vc vector 616 #define sz(a) (int)a.size() 617 #define forn(i, n) for (int i = 0; i < n; ++i) 618 #define pii pair <int, int> 619 #define vec pt 620 #define all(a) a.begin(), a.end() 621 622 const int K = 26; 623 const int N = 1e6 + 1; 624 625 struct node { 626 int next[K]; 627 int suf = -1, pr = -1, dp = 0, len = 0, ch = -1; 628 node () { 629 forn (i, K) next[i] = -1; 630 } 631 }; 632 633 int get (char c) { 634 if (c >= 'a') 635 return c - 'a'; 636 return c - 'A'; 637 } 638 639 int lst = 0, sz = 1; 640 node t[N * 2]; 641 int used[N * 2]; 642 643 int add (int a, int x) { 644 int b = sz++; 645 t[b].pr = a; 646 t[b].suf = 0; 647 t[b].ch = x; 648 for (; a != -1; a = t[a].suf) { 649 if (t[a].next[x] == -1) { 650 t[a].next[x] = b; 651 t[b].len = max(t[b].len, t[a].len + 1); 652 continue; 653 } 654 int c = t[a].next[x]; 655 if (t[c].pr == a) { 656 t[b].suf = c; 657 break; 658 } 659 int d = sz++; 660 forn (i, K) t[d].next[i] = t[c].next[i]; 661 t[d].suf = t[c].suf; 662 t[c].suf = t[b].suf = d; 663 t[d].pr = a; 664 t[d].ch = x; 665 for (; a != -1 && t[a].next[x] == c; a = t[a].suf) { 666 t[a].next[x] = d; 667 t[d].len = max(t[d].len, t[a].len + 1); 668 } 669 break; 670 } 671 return b; 672 } 673 674 void add (char c) { 675 lst = add(lst, get(c)); 676 } 677 678 void dfs (int u) { 679 used[u] = 1; 680 for (int i = 0; i < K; ++i) { 681 if (t[u].next[i] == -1) continue; 682 int v = t[u].next[i]; 683 if (!used[v]) 684 dfs(v); 685 t[u].dp += t[v].dp; 686 } 687 } 688 689 vc <int> p[N], pr; 690 int dr[N]; 691 vc <pii> d; 692 int l, r, cur = 0; 693 694 int cnt_log (int x, int y) { 695 int z = 1, res = 0; 696 while (y >= z) { 697 z *= x; 698 ++res; 699 } 700 return res - 1; 701 } 702 703 void rec (int i, int x) { 704 if (i == sz(d)) { 705 cur += l <= x; 706 return; 707 } 708 rec(i + 1, x); 709 for (int j = 1; j <= d[i].second; ++j) { 710 x *= d[i].first; 711 if (x > r) 712 break; 713 rec(i + 1, x); 714 } 715 } 716 717 void solve () { 718 int n; 719 cin >> n; 720 string s; 721 cin >> s; 722 for (char c : s) 723 add(c); 724 for (int a = lst; a != -1; a = t[a].suf) 725 t[a].dp = 1; 726 dfs(0); 727 for (int i = 2; i <= n; ++i) { 728 if (dr[i] == 0) { 729 dr[i] = i; 730 pr.pb(i); 731 } 732 for (int j = 0; j < sz(pr) && pr[j] <= dr[i] && i * pr[j] <= n; ++j) 733 dr[i * pr[j]] = pr[j]; 734 } 735 long long ans = 0; 736 forn (i, sz) { 737 if (t[i].len == 0) continue; 738 l = t[t[i].suf].len + 1; 739 r = t[i].len; 740 int x = t[i].dp; 741 d.clear(); 742 while (x > 1) { 743 int y = dr[x]; 744 if (d.empty() || d.back().first != y) 745 d.pb({y, 1}); 746 else 747 d.back().second++; 748 x /= y; 749 } 750 rec(0, 1); 751 ans += t[i].dp * cur; 752 cur = 0; 753 } 754 cout << ans << '\n'; 755 } 756 757 /* Starting and precalcing */ 758 signed main() { 759 /* freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); */ 760 fast; 761 int t = 1; 762 // cin >> t; 763 while (t--) solve(); 764 return 0; 765 } 766 ```