codeforces-scrape

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

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 ```