1114.md (37894B)
1 Source: https://codeforces.com/blog/entry/65136 2 3 *Model solutions are now available.* 4 *[GreenGrape](/profile/GreenGrape "Master GreenGrape") and I will write more about problem F, including an alternative data structures (still quite tight on time limit) ;)* 5 6 ## [1114A - Got Any Grapes?](/contest/1114/problem/A "Codeforces Round 538 (Div. 2)") 7 8 Author: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [GreenGrape](/profile/GreenGrape "Master GreenGrape") 9 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [GreenGrape](/profile/GreenGrape "Master GreenGrape"), [neko_nyaaaaaaaaaaaaaaaaa](/profile/neko_nyaaaaaaaaaaaaaaaaa "Master neko_nyaaaaaaaaaaaaaaaaa") 10 Editorialist: [AkiLotus](/profile/AkiLotus "Master AkiLotus") 11 12 **Tutorial** 13 14 First of all, we can see the grape preference is hierarchically inclusive: the grapes' types Andrew enjoys are some of those that Dmitry does, and Dmitry's favorites are included in Michal's. 15 16 Let's distribute the grapes to satisfy Andrew first, then to Dmitry, then Michal. If any of the following criteria is not satisfied (which means one of our friends is not happy), then we can immediately say that no distributions are available: 17 18 * Andrew must have at least *a* green grapes. So we need, *x* ≤ *a*. 19 * Dmitry can have purple grapes and/or the remaining green grapes. In other words, *y* ≤ *a* + *b* - *x* (the minus *x* is because *x* green grapes have been given to Andrew already). 20 * Michal can have grapes of any kinds. In other words, *z* ≤ *a* + *b* + *c* - *x* - *y* (similar explanations like above for both minus *x* and minus *y*). 21 22 If all three criteria are satisfied, then a grape distribution is possible. 23 24 Total complexity: . 25 26 **Solution (Akikaze)** 27 28 Submission link: [49737634](/contest/1114/submission/49737634 "Submission 49737634 by AkiLotus") 29 30 **Source code in plain text** 31 32 ``` 33 #pragma comment(linker, "/stack:247474112") 34 #pragma GCC optimize("Ofast") 35 36 #include <bits/stdc++.h> 37 using namespace std; 38 39 #define endl '\n' 40 41 int x, y, z, a, b, c; 42 43 void Input() { 44 cin >> x >> y >> z; 45 cin >> a >> b >> c; 46 } 47 48 void Solve() { 49 if (x > a) {cout << "NO\n"; return;} 50 if (x + y > a + b) {cout << "NO\n"; return;} 51 if (x + y + z > a + b + c) {cout << "NO\n"; return;} 52 cout << "YES\n"; 53 } 54 55 int main(int argc, char* argv[]) { 56 ios_base::sync_with_stdio(0); 57 cin.tie(NULL); Input(); Solve(); 58 return 0; 59 } 60 ``` 61 62 ## [1114B - Yet Another Array Partitioning Task](/contest/1114/problem/B "Codeforces Round 538 (Div. 2)") 63 64 Author: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") 65 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") 66 Editorialist: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999"), [neko_nyaaaaaaaaaaaaaaaaa](/profile/neko_nyaaaaaaaaaaaaaaaaa "Master neko_nyaaaaaaaaaaaaaaaaa") 67 68 **Tutorial** 69 70 In a perfect scenario, the maximum beauty of the original array is just a sum of *m*·*k* largest elements. 71 72 In fact, such scenario is always available regardless of the elements. 73 74 Let's denote *A* as the set of these *m*·*k* largest elements. The solution for us will be dividing the array into *k* segments, such that each segment contains exactly *m* elements of *A*. Just make a split between corresponding elements in the set *A*. 75 76 Depending on the way we find *m*·*k* largest elements, the time complexity might differ. 77 78 If we simply do so after sorting the entire array by usual means, the time complexity will be . 79 80 However, we can use [`std::nth_element` function](http://www.cplusplus.com/reference/algorithm/nth_element/) instead of sorting the entire array. The idea is to sort the array in such a way that, every elements not higher than a value *v* will be stored in the left side, other elements will stay on the right, and this works in linear time (a.k.a.  time complexity). 81 82 An example implementation of such ordering can be shown [here](https://cp-algorithms.com/sequences/k-th.html). 83 84 **Solution (xuanquang1999)** 85 86 Submission link: [49737896](/contest/1114/submission/49737896 "Submission 49737896 by AkiLotus") 87 88 **Source code in plain text** 89 90 ``` 91 #include <bits/stdc++.h> 92 93 using namespace std; 94 95 typedef pair<int, int> pii; 96 typedef long long ll; 97 98 int main() { 99 ios_base::sync_with_stdio(0); cin.tie(NULL); 100 101 int n, m, k; 102 cin >> n >> m >> k; 103 104 vector<pii> a(n); 105 for(int i = 0; i < n; ++i) { 106 cin >> a[i].first; 107 a[i].second = i; 108 } 109 110 sort(a.begin(), a.end(), greater<pii>()); 111 112 vector<int> ind(m*k); 113 ll sumBeauty = 0; 114 for(int i = 0; i < m*k; ++i) { 115 sumBeauty += a[i].first; 116 ind[i] = a[i].second; 117 } 118 119 sort(ind.begin(), ind.end()); 120 121 vector<int> division(k-1); 122 for(int i = 0; i < k-1; ++i) 123 division[i] = ind[(i+1)*m - 1]; 124 125 cout << sumBeauty << endl; 126 for(int p: division) 127 cout << p + 1 << " "; 128 129 return 0; 130 } 131 ``` 132 133 ## [1114C - Trailing Loves (or L'oeufs?)](/contest/1114/problem/C "Codeforces Round 538 (Div. 2)") 134 135 Author: [AkiLotus](/profile/AkiLotus "Master AkiLotus") 136 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [majk](/profile/majk "International Grandmaster majk"), [cdkrot](/profile/cdkrot "Grandmaster cdkrot") 137 Editorialist: [AkiLotus](/profile/AkiLotus "Master AkiLotus") 138 139 **Tutorial** 140 141 The problem can be reduced to the following: finding the maximum *r* that *n* ! is divisible by *b**r*. 142 143 By prime factorization, we will have the following: *b* = *p*1*y*1·*p*2*y*2·...·*p**m**y**m*. 144 145 In a similar manner, we will also have: *n* ! = *p*1*x*1·*p*2*x*2·...·*p**m**x**m*·*Q* (with *Q* being coprime to any *p**i* presented above). 146 147 The process of finding *p*1, *p*2, ..., *p**m*, *y*1, *y*2, ..., *y**m* can be done by normal prime factorization of the value *b*. 148 149 The process of finding *x*1, *x*2, ..., *x**m* is a little bit more tricky since the integer they were originated (*n* !) is too huge to be factorized manually. Still the factorial properties gave us another approach: for each *p**i*, we can do the following: 150 151 * Initially, denote *x**i* = 0. 152 * Repeatedly do the following: add  to *x**i*, then divide *n* by *p**i*. The loop ends when *n* is zero. 153 154 After all, we can obtain the final value *r* as of following: . 155 156 Total complexity:  (as the number of prime factors of an integer *b* will not surpass ). 157 158 **Solution (Akikaze)** 159 160 Submission link: [49738076](/contest/1114/submission/49738076 "Submission 49738076 by AkiLotus") 161 162 **Source code in plain text** 163 164 ``` 165 #pragma comment(linker, "/stack:247474112") 166 #pragma GCC optimize("Ofast") 167 168 #include <bits/stdc++.h> 169 using namespace std; 170 171 #define endl '\n' 172 173 long long n, b; 174 175 void Input() { 176 cin >> n >> b; 177 } 178 179 void Solve() { 180 long long ans = 1000000000000000000LL; 181 for (long long i=2; i<=b; i++) { 182 if (1LL * i * i > b) i = b; 183 int cnt = 0; 184 while (b % i == 0) {b /= i; cnt++;} 185 if (cnt == 0) continue; 186 long long tmp = 0, mul = 1; 187 while (mul <= n / i) {mul *= i; tmp += n / mul;} 188 ans = min(ans, tmp / cnt); 189 } 190 cout << ans << endl; 191 } 192 193 int main(int argc, char* argv[]) { 194 ios_base::sync_with_stdio(0); cin.tie(NULL); 195 Input(); Solve(); return 0; 196 } 197 ``` 198 199 ## [1114D - Flood Fill](/contest/1114/problem/D "Codeforces Round 538 (Div. 2)") 200 201 Author: [neko_nyaaaaaaaaaaaaaaaaa](/profile/neko_nyaaaaaaaaaaaaaaaaa "Master neko_nyaaaaaaaaaaaaaaaaa") 202 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [neko_nyaaaaaaaaaaaaaaaaa](/profile/neko_nyaaaaaaaaaaaaaaaaa "Master neko_nyaaaaaaaaaaaaaaaaa"), [cdkrot](/profile/cdkrot "Grandmaster cdkrot") 203 Editorialist: [neko_nyaaaaaaaaaaaaaaaaa](/profile/neko_nyaaaaaaaaaaaaaaaaa "Master neko_nyaaaaaaaaaaaaaaaaa"), [cdkrot](/profile/cdkrot "Grandmaster cdkrot") 204 205 **Tutorial** 206 207 This problem was inspired by the game Flood-it. It is apparently NP-hard. You can try out the game here. https://www.chiark.greenend.org.uk/\%7Esgtatham/puzzles/js/flood.html 208 209 **The first solution is rather straightforward.** Suppose squares [*L*, *R*] are flooded, then they are either of color *c**L* or *c**R*. We can define  as the minimum number of moves required to make the segment [*L*, *R*] monochromic: 210 211 *  is the least moves required to make the segment having color *c**L*. 212 *  is the least moves required to make the segment having color *c**R*. 213 214 **The second solution, which is the author's intended solution, is less so.** Note that the size of the component doesn't matter, so first "compress" the array so that every adjacent elements are different. We will work on this compressed array instead. 215 216 We want to maximize the number of turns that we can fill two adjacent squares instead of one. From a starting square, this maximum number of "saved" turns is equal to the longest common subsequence (LCS) of the array expanding to the two sides. The answer is the *N* — (maximum LCS over all starting squares) 217 218 This is equivalent to finding the longest odd size palindrome subsequence. In fact, it is the longest palindrome subsequence. For every even-sized palindrome subsequence, since adjacent elements are different, we can just insert an element in the middle and obtain a longer palindrome subsequence. 219 220 To find the longest palindrome subsequence, we can make a reversed copy of the array and find LCS of it with the original array. 221 222 Alternatively, we can also use the first solution on the compressed array, without needing the third parameter. 223 224 Time complexity: . 225 226 **Solution 1 (_kun_)** 227 228 Submission link: [49738289](/contest/1114/submission/49738289 "Submission 49738289 by AkiLotus") 229 230 **Source code in plain text** 231 232 ``` 233 // Dmitry _kun_ Sayutin (2019) 234 235 #include <bits/stdc++.h> 236 237 using std::cin; 238 using std::cout; 239 using std::cerr; 240 241 using std::vector; 242 using std::map; 243 using std::array; 244 using std::set; 245 using std::string; 246 247 using std::pair; 248 using std::make_pair; 249 250 using std::tuple; 251 using std::make_tuple; 252 using std::get; 253 254 using std::min; 255 using std::abs; 256 using std::max; 257 using std::swap; 258 259 using std::unique; 260 using std::sort; 261 using std::generate; 262 using std::reverse; 263 using std::min_element; 264 using std::max_element; 265 266 #ifdef LOCAL 267 #define LASSERT(X) assert(X) 268 #else 269 #define LASSERT(X) {} 270 #endif 271 272 template <typename T> 273 T input() { 274 T res; 275 cin >> res; 276 LASSERT(cin); 277 return res; 278 } 279 280 template <typename IT> 281 void input_seq(IT b, IT e) { 282 std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>); 283 } 284 285 #define SZ(vec) int((vec).size()) 286 #define ALL(data) data.begin(),data.end() 287 #define RALL(data) data.rbegin(),data.rend() 288 #define TYPEMAX(type) std::numeric_limits<type>::max() 289 #define TYPEMIN(type) std::numeric_limits<type>::min() 290 291 int dp[5000][5000][2]; 292 293 int main() { 294 std::iostream::sync_with_stdio(false); 295 cin.tie(nullptr); 296 cout.tie(nullptr); 297 298 // code here 299 int n = input<int>(); 300 301 vector<int> a(n); 302 input_seq(ALL(a)); 303 304 for (int i = 0; i != n; ++i) 305 for (int j = 0; j != n; ++j) 306 dp[i][j][0] = dp[i][j][1] = (i == j ? 0 : TYPEMAX(int) / 2); 307 308 309 for (int r = 0; r != n; ++r) 310 for (int l = r; l >= 0; --l) 311 for (int it = 0; it != 2; ++it) { 312 int c = (it == 0 ? a[l] : a[r]); 313 314 if (l) 315 dp[l - 1][r][0] = min(dp[l - 1][r][0], dp[l][r][it] + int(c != a[l - 1])); 316 317 if (r + 1 != n) 318 dp[l][r + 1][1] = min(dp[l][r + 1][1], dp[l][r][it] + int(c != a[r + 1])); 319 } 320 321 cout << min(dp[0][n - 1][0], dp[0][n - 1][1]) << "\n"; 322 323 return 0; 324 } 325 ``` 326 327 **Solution 2 (neko_nyaa)** 328 329 Submission link: [49738394](/contest/1114/submission/49738394 "Submission 49738394 by AkiLotus") 330 331 **Source code in plain text** 332 333 ``` 334 #include <bits/stdc++.h> 335 using namespace std; 336 337 const int maxN = 5008; 338 339 int n; 340 int dp[maxN][maxN]; 341 vector<int> a(1), b; 342 vector<int> ans; 343 344 void input() { 345 cin >> n; 346 for (int i = 0; i < n; i++) { 347 int x; cin >> x; 348 if (x != a.back()) a.push_back(x); 349 } 350 n = a.size() - 1; 351 352 b = a; 353 reverse(b.begin() + 1, b.end()); 354 } 355 356 void solve() { 357 for (int i = 1; i <= n; i++) { 358 for (int j = 1; j <= n; j++) { 359 if (a[i] == b[j]) {dp[i][j] = dp[i-1][j-1] + 1;} 360 else {dp[i][j] = max(dp[i-1][j], dp[i][j-1]);} 361 } 362 } 363 } 364 365 void output() { 366 cout << n - (dp[n][n] + 1)/2 << '\n'; 367 } 368 369 int main() { 370 371 input(); 372 solve(); 373 output(); 374 375 return 0; 376 } 377 ``` 378 379 ## [1114E - Arithmetic Progression](/contest/1114/problem/E "Codeforces Round 538 (Div. 2)") 380 381 Author: [AkiLotus](/profile/AkiLotus "Master AkiLotus") 382 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [GreenGrape](/profile/GreenGrape "Master GreenGrape") 383 Editorialist: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") 384 385 **Tutorial** 386 387 The `>` query type allows you to find the max value of the array through binary searching, which will cost  queries. 388 389 The remaining queries will be spent for the queries of the `?` type to get some random elements of the array. *d* will be calculated as greatest common divisors of all difference between all consecutive elements, provided all elements found (yes, including the `max` one) is kept into a list sorted by increasing order. 390 391 Having `d` and `max`, we can easily find the `min` value: *min* = *max* - *d*·(*n* - 1). 392 393 The number of allowed queries seem small (30 queries to be exact), yet it's enough for us to have reasonable probability of passing the problem. 394 395 *By some maths, we can find out the probability of our solution to fail being relatively small — approximately 1.86185·10- 9.* 396 397 **Proof on the probability, written by xuanquang1999** 398 399 For simplicity, assumed that the sequence *a* is [0, 1, 2, ..., *n* - 1]. Suppose that we randomly (and uniformly) select a subsequence *S* containing *k* elements from sequence *a* (when *k* is the number of `?` query asked). Denote *S* = [*s*1, *s*2, ..., *s**k*]. 400 401 Let *D* the GCD of all difference between consecutive elements in *S*. In other word, . Our solution will success if *D* = 1 and will fail otherwise. Let *P* the probability that our solution will pass (*D* = 1). Then the failing probability is 1 - *P*. 402 403 We will apply [Möbius inversion](https://codeforces.com/blog/entry/53925) to calculate *P*: Let *f*(*x*) the probability that *D* is divisible by *x*. Then,  (where μ(*x*) is the Möbius function). 404 405 Now we need to calculate *f*(*x*). It can be shown that *D* is divisible by *x* if and only if  for all 2 ≤ *i* ≤ *k*. In other word, there is some *r* from 0 to *x* - 1 such that  for all 1 ≤ *i* ≤ *k*. 406 407 Let *g*(*r*) the number of ways to select a subsequence *S* such that  for all 1 ≤ *i* ≤ *k*. Then, according to definition: 408 409  410 411 The denominator is simply . To calculate *g*(*r*), notice that for each *i*, the value of *s**i* can be *x*·*j* + *r* for some integer *j*. In other word, *S* must be a subsequence of the sequence *a**r* = [*r*, *x* + *r*, 2*x* + *r*, ...]. Let . 412 413 * If , *a**r* has *q* + 1 elements. Therefore,  414 * If , *a**r* has *q* elements. Therefore, . 415 416 In summary: 417 418  419 420 The complexity of this calculating method is *O*(*n*). My implementation of the above method can be found [here](https://ideone.com/IHmndY). 421 422 Keep in mind to use a good random number generator and a seed which is hard to obtain, thus making your solution truly random and not falling into corner cases. 423 424 Some of the tutorials of [neal](/profile/neal "International Grandmaster neal") might be helpful: 425 426 [Don't use rand(): a guide to random number generators in C++](https://codeforces.com/blog/entry/61587) 427 [How randomized solutions can be hacked, and how to make your solution unhackable](https://codeforces.com/blog/entry/61675) 428 429 **Solution (Akikaze)** 430 431 Submission link: [49739271](/contest/1114/submission/49739271 "Submission 49739271 by AkiLotus") 432 433 **Source code in plain text** 434 435 ``` 436 #pragma comment(linker, "/stack:247474112") 437 #pragma GCC optimize("Ofast") 438 439 #include <bits/stdc++.h> 440 using namespace std; 441 442 #define endl '\n' 443 mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count()); 444 445 int n, Max = -1000000000, d = 0; 446 int queryRemaining = 60; vector<int> id; 447 448 void findMax() { 449 int top = -1000000000, bot = +1000000000; 450 while (top <= bot) { 451 int hasHigher; 452 int mid = (top + bot) / 2; 453 cout << "> " << mid << endl; 454 fflush(stdout); cin >> hasHigher; 455 queryRemaining--; 456 if (hasHigher) top = mid + 1; 457 else {bot = mid - 1; Max = mid;} 458 } 459 } 460 461 void findD() { 462 vector<int> List; int RandomRange = n; 463 while (queryRemaining > 0 && RandomRange > 0) { 464 int demandedIndex = rng32() % RandomRange; 465 cout << "? " << id[demandedIndex] << endl; fflush(stdout); 466 int z; cin >> z; List.push_back(z); 467 RandomRange--; queryRemaining--; 468 swap(id[demandedIndex], id[RandomRange]); 469 } 470 sort(List.begin(), List.end()); 471 if (List.back() != Max) List.push_back(Max); 472 for (int i=1; i<List.size(); i++) { 473 d = __gcd(d, List[i] - List[i-1]); 474 } 475 } 476 477 void Input() { 478 cin >> n; id.resize(n); 479 for (int i=0; i<n; i++) id[i] = i+1; 480 } 481 482 void Solve() { 483 findMax(); findD(); 484 int Min = Max - d * (n - 1); 485 cout << "! " << Min << " " << d; 486 cout << endl; fflush(stdout); 487 } 488 489 int main(int argc, char* argv[]) { 490 ios_base::sync_with_stdio(0); 491 Input(); Solve(); return 0; 492 } 493 ``` 494 495 ## [1114F - Please, another Queries on Array?](/contest/1114/problem/F "Codeforces Round 538 (Div. 2)") 496 497 Author: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [cdkrot](/profile/cdkrot "Grandmaster cdkrot") 498 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [GreenGrape](/profile/GreenGrape "Master GreenGrape"), [cdkrot](/profile/cdkrot "Grandmaster cdkrot") 499 Editorialist: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [GreenGrape](/profile/GreenGrape "Master GreenGrape"), [cdkrot](/profile/cdkrot "Grandmaster cdkrot") 500 501 **Tutorial** 502 503 There's a few fundamentals about Euler's totient we need to know: 504 505 * φ(*p*) = *p* - 1 and φ(*p**k*) = *p**k* - 1·(*p* - 1), provided *p* is a prime number and *k* is a positive integer. You can easily prove these equations through the definition of the function itself. 506 * Euler's totient is a **multiplicative function**. *f*(*x*) is considered a multiplicative function when  means *f*(*a*)·*f*(*b*) = *f*(*a*·*b*). 507 508 Keep in mind that we can rewrite φ(*p**k*) as of following: . 509 510 Let's denote *P* as the set of prime factors of . 511 512 Thus, the answer for each query will simply be: . 513 514 So, for each query we'll need to know the product of the elements, and which primes are included in that product. 515 516 There are a few ways to work around with it. One of the most effective way is as following: 517 518 * Create a product segment tree to maintain the segment products. 519 * Since  only depends on the appearance or non-appearance of the primes, and the constraints guaranteed us to have at most 62 prime factors, we can use bitmasks and an or-sum segment tree to maintain this part. 520 521 Also, the bitmasks and range products can be maintained in a sqrt-decomposition fashion (please refer to [GreenGrape](/profile/GreenGrape "Master GreenGrape")'s solution), making each query's complexity to be somewhat around . Still, this complexity is quite high and surpassed time limit on a pretty thin margin. 522 523 Complexity for initializing segment trees: . 524 525 Complexity for each update query: . 526 527 Complexity for each return query: . 528 529 **Solution 1a (_kun_)** 530 531 Submission link: [49739509](/contest/1114/submission/49739509 "Submission 49739509 by AkiLotus") 532 533 **Source code in plain text** 534 535 ``` 536 // Dmitry _kun_ Sayutin (2019) 537 538 #include <bits/stdc++.h> 539 540 using std::cin; 541 using std::cout; 542 using std::cerr; 543 544 using std::vector; 545 using std::map; 546 using std::array; 547 using std::set; 548 using std::string; 549 550 using std::pair; 551 using std::make_pair; 552 553 using std::tuple; 554 using std::make_tuple; 555 using std::get; 556 557 using std::min; 558 using std::abs; 559 using std::max; 560 using std::swap; 561 562 using std::unique; 563 using std::sort; 564 using std::generate; 565 using std::reverse; 566 using std::min_element; 567 using std::max_element; 568 569 #ifdef LOCAL 570 #define LASSERT(X) assert(X) 571 #else 572 #define LASSERT(X) {} 573 #endif 574 575 template <typename T> 576 T input() { 577 T res; 578 cin >> res; 579 LASSERT(cin); 580 return res; 581 } 582 583 template <typename IT> 584 void input_seq(IT b, IT e) { 585 std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>); 586 } 587 588 #define SZ(vec) int((vec).size()) 589 #define ALL(data) data.begin(),data.end() 590 #define RALL(data) data.rbegin(),data.rend() 591 #define TYPEMAX(type) std::numeric_limits<type>::max() 592 #define TYPEMIN(type) std::numeric_limits<type>::min() 593 594 const int mod = 1000 * 1000 * 1000 + 7; 595 596 int add(int a, int b) { 597 return (a + b >= mod ? a + b - mod : a + b); 598 } 599 600 int sub(int a, int b) { 601 return (a >= b ? a - b : mod + a - b); 602 } 603 604 int mult(int a, int b) { 605 return (int64_t(a) * b) % mod; 606 } 607 608 int fpow(int a, int n, int r = 1) { 609 while (n) { 610 if (n % 2) 611 r = mult(r, a); 612 613 n /= 2; 614 a = mult(a, a); 615 } 616 617 return r; 618 } 619 620 const int max_n = 4.1e5; 621 int tree[4 * max_n]; 622 int modif[4 * max_n]; 623 int64_t pmask[4 * max_n], pushmask[4 * max_n]; 624 625 vector<int> primes, revprimes; 626 627 void build(int v, int l, int r, vector<int>& a) { 628 modif[v] = 1; 629 630 if (l == r - 1) { 631 tree[v] = a[l]; 632 633 for (int i = 0; i != SZ(primes); ++i) 634 if (a[l] % primes[i] == 0) 635 pmask[v] |= (int64_t(1) << int64_t(i)); 636 } else { 637 int m = l + (r - l) / 2; 638 build(2 * v + 1, l, m, a); 639 build(2 * v + 2, m, r, a); 640 641 tree[v] = mult(tree[2 * v + 1], tree[2 * v + 2]); 642 pmask[v] = pmask[2 * v + 1] | pmask[2 * v + 2]; 643 } 644 } 645 646 void push(int v, int vl, int vr) { 647 if (modif[v] != 1) 648 tree[v] = fpow(modif[v], vr - vl, tree[v]); 649 650 pmask[v] |= pushmask[v]; 651 652 if (vl != vr - 1) { 653 modif[2 * v + 1] = mult(modif[2 * v + 1], modif[v]); 654 modif[2 * v + 2] = mult(modif[2 * v + 2], modif[v]); 655 656 pushmask[2 * v + 1] |= pushmask[v]; 657 pushmask[2 * v + 2] |= pushmask[v]; 658 } 659 660 modif[v] = 1; 661 pushmask[v] = 0; 662 } 663 664 pair<int, int64_t> get(int v, int vl, int vr, int l, int r) { 665 if (vr <= l or r <= vl) 666 return make_pair<int, int64_t>(1, 0); 667 668 push(v, vl, vr); 669 670 if (l <= vl and vr <= r) 671 return make_pair(tree[v], pmask[v]); 672 673 int vm = vl + (vr - vl) / 2; 674 675 auto r1 = get(2 * v + 1, vl, vm, l, r); 676 auto r2 = get(2 * v + 2, vm, vr, l, r); 677 678 return make_pair(mult(r1.first, r2.first), r1.second | r2.second); 679 } 680 681 void multiply(int v, int vl, int vr, int l, int r, int x, int64_t mask) { 682 if (vr <= l or r <= vl) 683 return; 684 685 push(v, vl, vr); 686 687 if (l <= vl and vr <= r) { 688 pushmask[v] = mask; 689 modif[v] = x; 690 return; 691 } 692 693 int vm = vl + (vr - vl) / 2; 694 695 multiply(2 * v + 1, vl, vm, l, r, x, mask); 696 multiply(2 * v + 2, vm, vr, l, r, x, mask); 697 698 pmask[v] = pmask[2 * v + 1] | pmask[2 * v + 2] | pushmask[2 * v + 1] | pushmask[2 * v + 2]; 699 tree[v] = fpow(x, min(vr, r) - max(l, vl), tree[v]); 700 } 701 702 int main() { 703 std::iostream::sync_with_stdio(false); 704 cin.tie(nullptr); 705 cout.tie(nullptr); 706 707 // code here 708 for (int i = 2; i <= 300; ++i) { 709 bool ok = true; 710 for (int j = 2; j * j <= i and ok; ++j) 711 if (i % j == 0) 712 ok = false; 713 714 if (ok) { 715 primes.push_back(i); 716 revprimes.push_back(fpow(i, mod - 2)); 717 } 718 } 719 720 int n = input<int>(); 721 int q = input<int>(); 722 723 vector<int> a(n); 724 input_seq(ALL(a)); 725 726 build(0, 0, n, a); 727 728 for (int it = 0; it != q; ++it) { 729 if (input<string>() == "TOTIENT") { 730 int l = input<int>() - 1; 731 int r = input<int>() - 1; 732 733 pair<int, uint64_t> prod = get(0, 0, n, l, r + 1); 734 for (int i = 0; i != SZ(primes); ++i) 735 if (prod.second & (int64_t(1) << int64_t(i))) 736 prod.first = mult(mult(prod.first, primes[i] - 1), revprimes[i]); 737 738 cout << prod.first << "\n"; 739 } else { 740 int l = input<int>() - 1; 741 int r = input<int>() - 1; 742 int x = input<int>(); 743 744 int64_t msk = 0; 745 for (int i = 0; i != SZ(primes); ++i) 746 if (x % primes[i] == 0) 747 msk |= (int64_t(1) << int64_t(i)); 748 749 multiply(0, 0, n, l, r + 1, x, msk); 750 } 751 } 752 753 return 0; 754 } 755 ``` 756 757 **Solution 1b (Akikaze) [literally kun's solution, yet shorter, and a bit uglier :P]** 758 759 Submission link: [49740091](/contest/1114/submission/49740091 "Submission 49740091 by AkiLotus") 760 761 **Source code in plain text** 762 763 ``` 764 #pragma comment(linker, "/stack:247474112") 765 #pragma GCC optimize("Ofast") 766 767 #include <bits/stdc++.h> 768 using namespace std; 769 770 #define endl '\n' 771 772 const int Mod = 1000000007; 773 774 int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137 775 ,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293}; // (size = 62) 776 777 int modPow(int a, int b) { 778 int res = 1; 779 while (b > 0) { 780 if (b % 2 == 0) {a = (1LL * a * a) % Mod; b /= 2;} 781 else {res = (1LL * res * a) % Mod; b -= 1;} 782 } 783 return res; 784 } 785 786 struct ProTree { 787 vector<int> Tree, Lazy; 788 ProTree() {} 789 ProTree(int n) {Tree.resize(n*4, 1); Lazy.resize(n*4, 1);} 790 791 void Propagate(int node, int st, int en) { 792 if (Lazy[node] == 1) return; 793 Tree[node] = (1LL * Tree[node] * modPow(Lazy[node], (en - st + 1))) % Mod; 794 if (st != en) { 795 Lazy[node*2+1] = (1LL * Lazy[node*2+1] * Lazy[node]) % Mod; 796 Lazy[node*2+2] = (1LL * Lazy[node*2+2] * Lazy[node]) % Mod; 797 } 798 Lazy[node] = 1; 799 } 800 801 void Multiply(int node, int st, int en, int L, int R, int val) { 802 Propagate(node, st, en); 803 if (st > en || en < L || R < st) return; 804 if (L <= st && en <= R) { 805 Lazy[node] = (1LL * Lazy[node] * val) % Mod; 806 Propagate(node, st, en); return; 807 } 808 Multiply(node*2+1, st, (st+en)/2+0, L, R, val); 809 Multiply(node*2+2, (st+en)/2+1, en, L, R, val); 810 Tree[node] = (1LL * Tree[node*2+1] * Tree[node*2+2]) % Mod; 811 } 812 813 int Product(int node, int st, int en, int L, int R) { 814 Propagate(node, st, en); 815 if (st > en || en < L || R < st) return 1; 816 if (L <= st && en <= R) return Tree[node]; 817 int p1 = Product(node*2+1, st, (st+en)/2+0, L, R); 818 int p2 = Product(node*2+2, (st+en)/2+1, en, L, R); 819 return ((1LL * p1 * p2) % Mod); 820 } 821 }; 822 823 struct OrTree { 824 vector<long long> Tree, Lazy; 825 OrTree() {} 826 OrTree(int n) {Tree.resize(n*4); Lazy.resize(n*4);} 827 828 void Propagate(int node, int st, int en) { 829 if (Lazy[node] == 0) return; 830 Tree[node] |= Lazy[node]; 831 if (st != en) { 832 Lazy[node*2+1] |= Lazy[node]; 833 Lazy[node*2+2] |= Lazy[node]; 834 } 835 Lazy[node] = 0; 836 } 837 838 void Update(int node, int st, int en, int L, int R, long long val) { 839 Propagate(node, st, en); 840 if (st > en || en < L || R < st) return; 841 if (L <= st && en <= R) { 842 Lazy[node] |= val; 843 Propagate(node, st, en); return; 844 } 845 Update(node*2+1, st, (st+en)/2+0, L, R, val); 846 Update(node*2+2, (st+en)/2+1, en, L, R, val); 847 Tree[node] = (Tree[node*2+1] | Tree[node*2+2]); 848 } 849 850 long long Or(int node, int st, int en, int L, int R) { 851 Propagate(node, st, en); 852 if (st > en || en < L || R < st) return 0; 853 if (L <= st && en <= R) return Tree[node]; 854 long long p1 = Or(node*2+1, st, (st+en)/2+0, L, R); 855 long long p2 = Or(node*2+2, (st+en)/2+1, en, L, R); 856 return (p1 | p2); 857 } 858 }; 859 860 int N, Q, l, r, x; string cmd; 861 vector<int> invPrime(62); 862 vector<int> A; ProTree PrTree; OrTree OSTree; 863 vector<long long> Mask(301, 0); 864 865 void PreprocessMask() { 866 for (int z=1; z<=300; z++) { 867 for (int i=0; i<62; i++) { 868 if (z % prime[i] != 0) continue; 869 Mask[z] |= (1LL << i); 870 } 871 } 872 } 873 874 void Input() { 875 for (int i=0; i<62; i++) invPrime[i] = modPow(prime[i], Mod-2); PreprocessMask(); 876 cin >> N >> Q; A.resize(N); PrTree = ProTree(N); OSTree = OrTree(N); 877 for (int i=0; i<N; i++) { 878 cin >> A[i]; 879 PrTree.Multiply(0, 0, N-1, i, i, A[i]); 880 OSTree.Update(0, 0, N-1, i, i, Mask[A[i]]); 881 } 882 } 883 884 void Solve() { 885 while (Q--) { 886 cin >> cmd >> l >> r; l--; r--; 887 if (cmd == "MULTIPLY") { 888 cin >> x; 889 PrTree.Multiply(0, 0, N-1, l, r, x); 890 OSTree.Update(0, 0, N-1, l, r, Mask[x]); 891 } 892 else if (cmd == "TOTIENT") { 893 int res = PrTree.Product(0, 0, N-1, l, r); 894 long long SegMask = OSTree.Or(0, 0, N-1, l, r); 895 for (int i=0; i<62; i++) { 896 if ((SegMask & (1LL << i)) == 0) continue; 897 res = (1LL * res * (prime[i] - 1)) % Mod; 898 res = (1LL * res * invPrime[i]) % Mod; 899 } 900 cout << res << endl; 901 } 902 } 903 } 904 905 int main(int argc, char* argv[]) { 906 ios_base::sync_with_stdio(0); cin.tie(NULL); 907 Input(); Solve(); return 0; 908 } 909 ``` 910 911 **Solution 2 (GreenGrape)** 912 913 Submission link: [49739611](/contest/1114/submission/49739611 "Submission 49739611 by AkiLotus") 914 915 **Source code in plain text** 916 917 ``` 918 #define _CRT_SECURE_NO_WARNINGS 919 #pragma GCC optimize("unroll-loops") 920 #include <iostream> 921 #include <algorithm> 922 #include <vector> 923 #include <ctime> 924 #include <unordered_set> 925 #include <string> 926 #include <map> 927 #include <unordered_map> 928 #include <random> 929 #include <set> 930 #include <cassert> 931 #include <functional> 932 #include <iomanip> 933 #include <queue> 934 #include <numeric> 935 #include <bitset> 936 #include <iterator> 937 938 using namespace std; 939 940 const int N = 100001; 941 942 mt19937 gen(time(NULL)); 943 #define forn(i, n) for (int i = 0; i < n; i++) 944 #define ford(i, n) for (int i = n - 1; i >= 0; i--) 945 #define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr) 946 #define all(a) (a).begin(), (a).end() 947 #define pii pair<int, int> 948 #define mp make_pair 949 #define endl '\n' 950 #define vi vector<int> 951 952 typedef long long ll; 953 954 template<typename T = int> 955 inline T read() { 956 T val = 0, sign = 1; char ch; 957 for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) 958 if (ch == '-') sign = -1; 959 for (; ch >= '0' && ch <= '9'; ch = getchar()) 960 val = val * 10 + ch - '0'; 961 return sign * val; 962 } 963 964 const int mod = 1e9 + 7; 965 const int phi = 1e9 + 6; 966 967 const int M = 301, B = 500; 968 int P = 0; 969 970 inline int mul(int a, int b) { 971 return (a * 1LL * b) % mod; 972 } 973 974 int mpow(int u, int p) { 975 if (!p) return 1; 976 return mul(mpow(mul(u, u), p / 2), (p & 1) ? u : 1); 977 } 978 979 vector<int> primes; 980 vector<int> pi; 981 982 int pw[M]; 983 int lg[N]; 984 985 bool pr(int x) { 986 if (x <= 1) return false; 987 for (int i = 2; i * i <= x; i++) 988 if (x % i == 0) 989 return false; 990 return true; 991 } 992 993 void precalc() { 994 forn(i, M) 995 if (pr(i)) { 996 primes.push_back(i); 997 P++; 998 } 999 pi.resize(P); 1000 forn(i, M) { 1001 int x = 1; 1002 forn(j, B) { 1003 x = mul(x, i); 1004 } 1005 pw[i] = x; 1006 } 1007 1008 forn(i, P) 1009 pi[i] = mpow(primes[i], phi - 1); 1010 } 1011 1012 struct product_tree { 1013 vector<int> arr, block_product, block_update, single_update; 1014 int n; 1015 1016 product_tree(vector<int>& a) : n(a.size()) { 1017 arr = a; 1018 while (n % B) { 1019 n++, arr.push_back(1); 1020 } 1021 block_product.resize(n / B, 1); 1022 block_update.resize(n / B, -1); 1023 single_update.resize(n / B, -1); 1024 1025 for (int i = 0; i < n; i += B) { 1026 int x = 1; 1027 int pos = i / B; 1028 forn(j, B) 1029 x = mul(x, arr[i + j]); 1030 block_product[pos] = x; 1031 } 1032 } 1033 1034 inline void add(int& u, int x, int mode) { 1035 if (mode) { 1036 if (u == -1) 1037 u = x; 1038 else 1039 u = mul(u, x); 1040 } 1041 else { 1042 if (u == -1) 1043 u = pw[x]; 1044 else 1045 u = mul(u, pw[x]); 1046 } 1047 } 1048 1049 void update(int pos, int x) { 1050 add(block_update[pos], x, 0); 1051 add(single_update[pos], x, 1); 1052 } 1053 1054 void reconstruct(int pos) { 1055 int e = single_update[pos]; 1056 if (e == -1) return; 1057 int x = 1; 1058 1059 int l = pos * B, r = l + B; 1060 for (int i = l; i < r; i++) { 1061 arr[i] = mul(arr[i], e); 1062 x = mul(x, arr[i]); 1063 } 1064 1065 single_update[pos] = block_update[pos] = -1; 1066 block_product[pos] = x; 1067 } 1068 1069 void apply(int l, int r, int x) { 1070 int L = l / B, R = r / B; 1071 if (L == R) { 1072 reconstruct(L); 1073 for (int i = l; i <= r; i++) { 1074 arr[i] = mul(arr[i], x); 1075 block_product[L] = mul(block_product[L], x); 1076 } 1077 return; 1078 } 1079 reconstruct(L); 1080 for (int i = l; i < (L + 1) * B; i++) { 1081 arr[i] = mul(arr[i], x); 1082 block_product[L] = mul(block_product[L], x); 1083 } 1084 reconstruct(R); 1085 for (int i = R * B; i <= r; i++) { 1086 arr[i] = mul(arr[i], x); 1087 block_product[R] = mul(block_product[R], x); 1088 } 1089 for (int j = L + 1; j < R; j++) 1090 update(j, x); 1091 } 1092 1093 int get(int l, int r) { 1094 int L = l / B, R = r / B; 1095 int ans = 1; 1096 if (L == R) { 1097 reconstruct(L); 1098 for (int i = l; i <= r; i++) { 1099 ans = mul(ans, arr[i]); 1100 } 1101 return ans; 1102 } 1103 reconstruct(L); 1104 for (int i = l; i < (L + 1) * B; i++) { 1105 ans = mul(ans, arr[i]); 1106 } 1107 reconstruct(R); 1108 for (int i = R * B; i <= r; i++) { 1109 ans = mul(ans, arr[i]); 1110 } 1111 for (int j = L + 1; j < R; j++) { 1112 ans = mul(ans, block_product[j]); 1113 if (block_update[j] != -1) 1114 ans = mul(ans, block_update[j]); 1115 } 1116 return ans; 1117 } 1118 }; 1119 1120 struct prime_tree { 1121 vector<ll> t, d; 1122 int n; 1123 1124 prime_tree(vector<ll>& a) : n(a.size()) { 1125 t.resize(4 * n); 1126 d.resize(4 * n, -1); 1127 build(1, 0, n, a); 1128 } 1129 1130 ll build(int u, int l, int r, vector<ll>& a) { 1131 if (l == r - 1) { 1132 return t[u] = a[l]; 1133 } 1134 int m = (l + r) / 2; 1135 return t[u] = build(u << 1, l, m, a) | build(u << 1 | 1, m, r, a); 1136 } 1137 1138 inline void add(ll& u, ll x) { 1139 if (u == -1) 1140 u = x; 1141 else 1142 u |= x; 1143 } 1144 1145 void push(int u, int l, int r) { 1146 if (d[u] == -1) return; 1147 t[u] |= d[u]; 1148 if (r - l > 1) { 1149 add(d[u << 1], d[u]); 1150 add(d[u << 1 | 1], d[u]); 1151 } 1152 d[u] = -1; 1153 } 1154 1155 void update(int u, int l, int r, int L, int R, ll x) { 1156 push(u, l, r); 1157 if (L >= R || l > L || r < R) return; 1158 if (l == L && r == R) { 1159 add(d[u], x); 1160 push(u, l, r); 1161 return; 1162 } 1163 int m = (l + r) / 2; 1164 update(u << 1, l, m, L, min(m, R), x); 1165 update(u << 1 | 1, m, r, max(L, m), R, x); 1166 1167 t[u] = t[u << 1] | t[u << 1 | 1]; 1168 } 1169 1170 ll get(int u, int l, int r, int L, int R) { 1171 push(u, l, r); 1172 if (L >= R || l > L || r < R) return 0; 1173 if (l == L && r == R) { 1174 return t[u]; 1175 } 1176 int m = (l + r) / 2; 1177 return get(u << 1, l, m, L, min(m, R)) | get(u << 1 | 1, m, r, max(L, m), R); 1178 } 1179 1180 ll get(int l, int r) { 1181 return get(1, 0, n, l, r + 1); 1182 } 1183 void apply(int l, int r, ll x) { 1184 update(1, 0, n, l, r + 1, x); 1185 } 1186 }; 1187 1188 ll transform(int x) { 1189 ll mask = 0; 1190 forn(i, P) 1191 if (x % primes[i] == 0) { 1192 mask |= (1LL << i); 1193 } 1194 return mask; 1195 } 1196 1197 void solve() { 1198 int n, q; cin >> n >> q; 1199 1200 vi a(n); 1201 vector<ll> _a; 1202 1203 for (auto& v : a) { 1204 cin >> v; 1205 _a.push_back(transform(v)); 1206 } 1207 1208 auto Ptree = product_tree(a); 1209 auto Mtree = prime_tree(_a); 1210 1211 int l, r, x; 1212 forn(i, q) { 1213 string s; cin >> s; 1214 if (s == "MULTIPLY") { 1215 cin >> l >> r >> x; 1216 l--, r--; 1217 Ptree.apply(l, r, x); 1218 Mtree.apply(l, r, transform(x)); 1219 } 1220 else { 1221 cin >> l >> r; 1222 l--, r--; 1223 1224 int product = Ptree.get(l, r); 1225 ll mask = Mtree.get(l, r); 1226 1227 forn(j, 63) 1228 if (mask >> j & 1) { 1229 product = mul(product, primes[j] - 1); 1230 product = mul(product, pi[j]); 1231 } 1232 1233 cout << product << endl; 1234 } 1235 } 1236 } 1237 1238 signed main() { 1239 int t = 1; 1240 1241 ios_base::sync_with_stdio(0); 1242 cin.tie(0); 1243 1244 precalc(); 1245 1246 while (t--) { 1247 clock_t z = clock(); 1248 solve(); 1249 debug("Total Time: %.3f\n", (double)(clock() - z) / CLOCKS_PER_SEC); 1250 } 1251 } 1252 ```