2205.md (26076B)
1 Source: https://codeforces.com/blog/entry/151310 2 3 Thank you for participating and accompanying Simons! We hope you enjoyed the problems. 4 5 **Rate the contest!** 6 7 * Horrible contest 8 * Bad contest 9 * Average contest 10 * Good contest 11 * Epic contest 12 13 **Rate the difficulty!** 14 15 * Impossible contest 16 * Hard contest 17 * Average contest 18 * Simple contest 19 * Trivial contest 20 21 **Rating Predictions** 22 23 | | A | B | C | D | E | F | G | 24 | --- | --- | --- | --- | --- | --- | --- | --- | 25 | [Leftist_G](/profile/Leftist_G "Master Leftist_G") | 800 | 800 | 1400 | 2000 | 2400 | 2600 | 2900 | 26 | [cool_milo](/profile/cool_milo "Master cool_milo") | 800 | 800 | 1400 | 1800 | 2400 | 2700 | 3300 | 27 | [StayAlone](/profile/StayAlone "Master StayAlone") | 800 | 900 | 1500 | 1900 | 2300 | 2200 | 2800 | 28 | [liuhangxin](/profile/liuhangxin "International Master liuhangxin") | 800 | 900 | 1000 | 1300 | | 2500 | 3100 | 29 | [_istil](/profile/_istil "Grandmaster _istil") | 800 | 1000 | 1400 | 1600 | 2100 | 2400 | 2600 | 30 | [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan") | 800 | 1000 | 1400 | 1800 | 2100 | 2400 | 2600 | 31 | [yanghanyv](/profile/yanghanyv "Candidate Master yanghanyv") | 800 | 900 | 1300 | 1400 | | 1900 | | 32 | [Comentropy](/profile/Comentropy "Expert Comentropy") | 800 | 1000 | 1600 | 1600 | | 2300 | | 33 | [wangzirui123](/profile/wangzirui123 "Grandmaster wangzirui123") | 800 | 1000 | 1700 | 2000 | 2600 | 2100 | 2900 | 34 35 | | A | B | C | D | E | F | G | 36 | --- | --- | --- | --- | --- | --- | --- | --- | 37 | **Average** | 800 | 922 | 1411 | 1711 | 2317 | 2344 | 2886 | 38 39 #### [2205A — Simons and Making It Beautiful](https://codeforces.com/contest/2205/problem/A) 40 41 **Rate the problem!** 42 43 * Horrible problem 44 * Bad problem 45 * Average problem 46 * Good problem 47 * Epic problem 48 * Did not solve 49 50 Author: [StayAlone](/profile/StayAlone "Master StayAlone") 51 52 Solution: [StayAlone](/profile/StayAlone "Master StayAlone") 53 54 **Hint 1** 55 56 Which index is always *ugly*? 57 58 **Hint 2** 59 60 Consider the lower bound of the answer. 61 62 **Tutorial** 63 64 Observe that index $n$ is always *ugly*, so the answer is at least $1$. 65 66 It remains to show that this lower bound is achievable. 67 68 Set $p_1\gets n$ so that for each $i$, $\max(p_1,p_2,\cdots,p_i)=n$. As a result, the only *ugly* index is $n$. 69 70 **Code (C++)** 71 72 By [StayAlone](/profile/StayAlone "Master StayAlone"). 73 74 ``` 75 #include <bits/stdc++.h> 76 using namespace std; 77 int n, a[505]; 78 79 void solve() { 80 cin >> n; 81 for(int i = 1; i <= n; i++) { 82 cin >> a[i]; 83 if (a[i] == n) swap(a[1], a[i]); 84 } 85 for(int i = 1; i <= n; i++) printf("%d ", a[i]); puts(""); 86 } 87 88 int main() { 89 int T; 90 cin >> T; 91 for (; T--; ) solve(); 92 return 0; 93 } 94 ``` 95 96 #### [2205B — Simons and Cakes for Success](https://codeforces.com/contest/2205/problem/B) 97 98 **Rate the problem!** 99 100 * Horrible problem 101 * Bad problem 102 * Average problem 103 * Good problem 104 * Epic problem 105 * Did not solve 106 107 Author: [Leftist_G](/profile/Leftist_G "Master Leftist_G") 108 109 Solution: [Leftist_G](/profile/Leftist_G "Master Leftist_G") 110 111 **Hint 1** 112 113 Consider the prime decomposition of the given $n$. 114 115 **Hint 2** 116 117 $n$ has at most $1$ prime divisor not smaller than $\sqrt n$. 118 119 **Tutorial** 120 121 Let $n=\prod p_i^{\alpha_i}$ be the prime factorization of $n$. Hence, if $n$ is a divisor of $k^n$, each $p_i$ must be a divisor of $k^n$ and then $k$. 122 123 Under constraints above, the minimum valid number is $k=\prod p_i$. Due to $\alpha_i\le n$, each $p_i^{\alpha_i}$ will be a divisor of $p_i^n$, so $n$ is a divisor of $k^n$. 124 125 Thus, we only need to find $\prod p_i$. Because $n$ has at most $1$ prime divisor not smaller than $\sqrt n$, we only need to check the prime numbers smaller than $\sqrt n$, and the remaining part is $1$ or the only prime divisor bigger than $\sqrt n$. 126 127 So we solve the problem in $\mathcal O(\sqrt n)$. 128 129 **Code (C++)** 130 131 By [Leftist_G](/profile/Leftist_G "Master Leftist_G"). 132 133 ``` 134 #include <bits/stdc++.h> 135 using namespace std; 136 const int N = 1e5 + 10; 137 int tc; 138 int n; 139 vector <int> pr; 140 bool vis[N]; 141 void init(int n = 31623){ 142 for(int i = 2; i <= n; i++){ 143 if(!vis[i]) pr.push_back(i); 144 for(auto j: pr){ 145 if(i * j > n) break; 146 vis[i * j]=1; 147 if(i % j == 0) break; 148 } 149 } 150 } 151 void solve(){ 152 cin>>n; 153 int ans = 1; 154 for(auto i: pr){ 155 if(n % i == 0){ 156 ans *= i; 157 while(n % i == 0) n /= i; 158 } 159 } 160 ans *= n; 161 cout << ans << '\n'; 162 } 163 int main(){ 164 ios::sync_with_stdio(false); 165 init(); 166 cin >> tc; 167 while(tc--) solve(); 168 } 169 ``` 170 171 **Code (Python)** 172 173 By [StayAlone](/profile/StayAlone "Master StayAlone"). 174 175 ``` 176 import sys 177 import math 178 179 def read_int(): 180 return int(sys.stdin.readline().strip()) 181 182 def solve(): 183 n = read_int() 184 ans = 1 185 for i in range(2, int(math.sqrt(n)) + 1): 186 if n % i == 0: 187 ans *= i 188 while n % i == 0: 189 n //= i 190 print(ans * n) 191 192 T = read_int() 193 for _ in range(T): 194 solve() 195 ``` 196 197 #### [2205C — Simons and Posting Blogs](https://codeforces.com/contest/2205/problem/C) 198 199 **Rate the problem!** 200 201 * Horrible problem 202 * Bad problem 203 * Average problem 204 * Good problem 205 * Epic problem 206 * Did not solve 207 208 Author: [Leftist_G](/profile/Leftist_G "Master Leftist_G") 209 210 Solution: [Leftist_G](/profile/Leftist_G "Master Leftist_G") 211 212 **Hint 1** 213 214 For an array $a_i$, only the last occurrence of each element matters. Therefore, the problem reduces to the case where all elements in one array are distinct. 215 216 **Hint 2** 217 218 Think the process in reverse. 219 220 **Tutorial** 221 222 Also, throughout the **whole process**, only the last occurrence of each element matters, so we may determine the order by working backwards. 223 224 Fix an order (in reverse). For each array in this order, we iterate through its elements. If an element is already contained in $Q$, ignore it. Otherwise, append it to the end of $Q$. 225 226 Thus, at each step, we choose the array that is lexicographically smallest among the remaining ones. Then, for the remaining arrays, we only keep the elements that are not contained in $Q$. Comparing two arrays takes $\mathcal O(\min{|a_i|, |a_j|})$, we can solve the problem with total time complexity $\mathcal O(n^2+n\sum l_i)$. 227 228 **Code (C++)** 229 230 By [StayAlone](/profile/StayAlone "Master StayAlone"). 231 232 ``` 233 #include <bits/stdc++.h> 234 #define rep1(i, l, r) for (int i = l; i <= int(r); ++i) 235 using namespace std; 236 const int MAXN = 1e6 + 10, inf = ~0U >> 2; 237 int n, vis[MAXN], chg[8010]; vector <int> a[8010]; 238 239 void init(vector <int> &now) { 240 for (auto &v : now) cin >> v, vis[v] = 0; 241 reverse(begin(now), end(now)); 242 vector <int> nw; 243 for (auto v : now) if (!vis[v]) nw.emplace_back(v), vis[v] = 1; 244 for (auto v : nw) vis[v] = 0; 245 now = nw; 246 } 247 248 void change(vector <int> &now) { 249 if (now.size() == 1 && now[0] == inf) return; 250 vector <int> nw; 251 for (auto v : now) if (!vis[v]) nw.emplace_back(v); 252 now = nw; 253 } 254 255 void solve() { 256 cin >> n; 257 rep1(i, 1, n) { 258 int _; 259 cin >> _; 260 a[i].resize(_); init(a[i]); chg[i] = 0; 261 } 262 rep1(i, 1, n) { 263 int id = 1; 264 rep1(j, 1, n) if (!chg[j] && a[j] < a[id]) id = j; 265 auto &now = a[id]; 266 for (auto v : now) printf("%d ", v), vis[v] = 1; 267 now = vector <int> {inf}; chg[id] = 1; 268 rep1(j, 1, n) if (!chg[j]) change(a[j]); 269 } puts(""); 270 } 271 272 int main() { 273 int T; 274 cin >> T; 275 for (; T--; ) solve(); 276 return 0; 277 } 278 ``` 279 280 #### [2205D — Simons and Beating Peaks](https://codeforces.com/contest/2205/problem/D) 281 282 **Rate the problem!** 283 284 * Horrible problem 285 * Bad problem 286 * Average problem 287 * Good problem 288 * Epic problem 289 * Did not solve 290 291 Author: [cool_milo](/profile/cool_milo "Master cool_milo") 292 293 Solution: [cool_milo](/profile/cool_milo "Master cool_milo"), [Leftist_G](/profile/Leftist_G "Master Leftist_G") 294 295 **Hint 1** 296 297 Simons's goal of minimizing operations means that the remaining array should be as long as possible. 298 299 **Hint 2** 300 301 Which element is absolutely impossible to remove? 302 303 **Hint 3** 304 305 The position of the maximum value cannot be removed, and we can see that splitting the array from the maximum value will result in two independent parts. 306 307 **Hint 4** 308 309 Consider the [Cartesian tree](https://en.wikipedia.org/wiki/Cartesian_tree) of the given permutation. 310 311 **Tutorial** 312 313 It's noticed that the maximum number of each number cannot be moved, and either the left side or the right side will be removed completely, so we can solve both sides separately. 314 315 The maximum number of both sides cannot be removed, either. Accordingly, they became the same problem with smaller scale. 316 317 Build the Cartesian tree for the sequence. It's easy to see that any path from the root corresponds to a way to keep the maximum number on one side and delete the others. 318 319 Calculate the depth of each node $d_u$, then the answer is $n - \max d_u$. 320 321 The solution could be done in $\Theta(n)$, and there are also solutions based on Dynamic Programming (DP) for time complexity $\tilde O(n)$. 322 323 **Code (C++)** 324 325 By [yanghanyv](/profile/yanghanyv "Candidate Master yanghanyv"). 326 327 ``` 328 #include <bits/stdc++.h> 329 using namespace std; 330 const int N=5e5+5; 331 int t,n,a[N],del[N],stk[N],top,ans; 332 void init(){ 333 for(int i=1;i<=n;i++){ 334 del[i]=0; 335 } 336 ans=n; 337 } 338 int main(){ 339 scanf("%d",&t); 340 while(t--){ 341 scanf("%d",&n); 342 init(); 343 for(int i=1;i<=n;i++){ 344 scanf("%d",&a[i]); 345 } 346 top=0; 347 for(int i=1;i<=n;i++){ 348 while(top&&a[stk[top]]<a[i]){ 349 top--; 350 } 351 stk[++top]=i; 352 del[i]+=i-top; 353 } 354 top=0; 355 for(int i=n;i>=1;i--){ 356 while(top&&a[stk[top]]<a[i]){ 357 top--; 358 } 359 stk[++top]=i; 360 del[i]+=n-i+1-top; 361 } 362 for(int i=1;i<=n;i++){ 363 ans=min(ans,del[i]); 364 } 365 printf("%d\n",ans); 366 } 367 return 0; 368 } 369 ``` 370 371 #### [2205E — Simons and Dividing the Rhythm](https://codeforces.com/contest/2205/problem/E) 372 373 **Rate the problem!** 374 375 * Horrible problem 376 * Bad problem 377 * Average problem 378 * Good problem 379 * Epic problem 380 * Did not solve 381 382 Author: [Leftist_G](/profile/Leftist_G "Master Leftist_G") 383 384 Solution: [Leftist_G](/profile/Leftist_G "Master Leftist_G") 385 386 **Hint 1** 387 388 Consider applying Dynamic Programming (DP) to solve the problem. What may the state be? 389 390 **Hint 2** 391 392 Assign a unique way to operate $s$ to $t$ for every different $s$. 393 394 **Hint 3** 395 396 For any $[l_i, r_i]$ you chose, consider the border of $t_{[l_i, r_i]}$. A border of an array $a[1 \sim n]$ means the subarray $a[1,l]$ such that $a[1,l] = a[n - l + 1,n]$. 397 398 **Tutorial** 399 400 Let's apply Dynamic Programming to the problem. 401 402 Assume $dp_i$ represents the different arrays $s[1:i]$ can generate $t[1:i]$. 403 404 to update $dp_{i + 1}$, consider the last subarray in the decomposition $dp_{[a, i + 1]}$. To ensure no duplicate counting, $dp_{[a, i + 1]}$ can't have a border. Which is to say, for any $s$ which could be operated to $t$, it could be realized by decomposing $s$ into subarrays without a border and reversing them. 405 406 Why can the solution above calculate the answer correctly? 407 408 **Proof.** 409 410 Recall that a border of an array $a[1 \sim n]$ means the subarray $a[1,l]$ such that $a[1,l] = a[n - l + 1,n]$. 411 412 For two different ways to operate $s$, assume the first different pair of decomposition of $s$ be $[l, r_1], [l, r_2] (r_1 \lt r_2)$, then $s_{[r_2 - r_1 + l, r_2]} = s_{[l, r_1]}$ since after flipping, they will be mapped to the same place in $t$. So $[l, r_2]$ has a border. 413 414 So by taking the shortest possible length of the next segment $[a, b]$ every time, we can find a solution without a border. (If there's a border $s_{[a, r]} = s_{[l, b]}$, we can show that the length of shortest border $B \lt \frac{b - a + 1}{2}$ . So $r \lt l$ holds. We could reverse $s_{[a, r]}, s_{[r + 1, l]}, s_{[l, b]}$ seperately to achieve the same goal.) 415 416 To check if any $dp_{[l, r]}$ has a border, we need to apply the KMP algorithm (starting from $t_{1 \sim n}$)for $n$ times, whose time complexity is $O(n^2)$. The dp progress also takes $O(n^2)$ time. So the total time complexity is $O(n^2)$. 417 418 **Code (C++)** 419 420 By [Leftist_G](/profile/Leftist_G "Master Leftist_G"). 421 422 ``` 423 #include <bits/stdc++.h> 424 #define fr1(i, a, b) for (int i = a; i <= b; i++) 425 #define fr2(i, a, b) for (int i = a; i >= b; i--) 426 using namespace std; 427 const int N = 1e5 + 10; 428 const int mod = 998244353; 429 int tc; 430 int n; 431 int a[N]; 432 int dp[N]; 433 int kmp[N]; 434 void add(int & x, int y) { 435 x += y; 436 if (x >= mod) x -= mod; 437 } 438 void solve() { 439 cin >> n; 440 fr1(i, 1, n) cin >> a[i]; 441 dp[0] = 1; 442 fr1(i, 1, n) dp[i] = 0; 443 fr1(i, 1, n) { 444 kmp[i] = i + 1; 445 int poi = i + 1; 446 fr2(j, i - 1, 1) { 447 while (a[j] != a[poi - 1] && poi != i + 1) poi = kmp[poi]; 448 if (a[j] == a[poi - 1]) poi--; 449 kmp[j] = poi; 450 } 451 fr2(j, i, 1) { 452 if (kmp[j] == i + 1) add(dp[i], dp[j - 1]); 453 } 454 } 455 cout << dp[n] << '\n'; 456 } 457 int main() { 458 ios::sync_with_stdio(false); 459 cin >> tc; 460 while (tc--) solve(); 461 } 462 ``` 463 464 #### [2205F — Simons and Reconstructing His Roads](https://codeforces.com/contest/2205/problem/F) 465 466 **Rate the problem!** 467 468 * Horrible problem 469 * Bad problem 470 * Average problem 471 * Good problem 472 * Epic problem 473 * Did not solve 474 475 Author: [cool_milo](/profile/cool_milo "Master cool_milo"), [Leftist_G](/profile/Leftist_G "Master Leftist_G") 476 477 Solution: [cool_milo](/profile/cool_milo "Master cool_milo"), [StayAlone](/profile/StayAlone "Master StayAlone") 478 479 **Hint 1** 480 481 Consider the case without any "accidents", i.e., when there are no additional restrictions on the reconstructed streets. 482 483 **Hint 2** 484 485 Observe the structure of a valid solution and try to construct a kind of "basis". 486 487 **Tutorial** 488 489 We can define each basis as a square, and assign its value as follows: 490 491  492 493 Now, it is easy to see that any subset of the bases forms a valid solution, and conversely, any valid solution can be decomposed into such bases. 494 495 Now consider a street that cannot be reconstructed. This implies that the two bases it connects must have the same state — either both are chosen, or both are not chosen. Therefore, we can use a DSU to maintain these constraints. The overall time complexity is $\mathcal O(nm\alpha(nm))$. 496 497 **Code (C++)** 498 499 By [yanghanyv](/profile/yanghanyv "Candidate Master yanghanyv"). 500 501 ``` 502 #include <bits/stdc++.h> 503 #define ll long long 504 using namespace std; 505 const int N=2e5+5; 506 const int M=4e5+5; 507 int t,n,m,fa[M]; 508 ll s[M],ans; 509 vector<int> w[N],v[N]; 510 void init(){ 511 for(int i=1;i<=n;i++){ 512 w[i].clear(); 513 v[i].clear(); 514 } 515 for(int i=0;i<=(n-1)*(m-1);i++){ 516 fa[i]=i; 517 s[i]=0; 518 } 519 ans=0; 520 } 521 int idx(int x,int y){ 522 return x>=1&&x<n&&y>=1&&y<m?(x-1)*(m-1)+y:0; 523 } 524 int find(int x){ 525 return fa[x]!=x?fa[x]=find(fa[x]):fa[x]; 526 } 527 void merge(int a,int b){ 528 if(find(a)!=find(b)){ 529 fa[find(a)]=find(b); 530 } 531 } 532 int main(){ 533 scanf("%d",&t); 534 while(t--){ 535 scanf("%d%d",&n,&m); 536 init(); 537 for(int i=1;i<n;i++){ 538 w[i].resize(m+1); 539 for(int j=1;j<=m;j++){ 540 scanf("%d",&w[i][j]); 541 } 542 } 543 for(int i=1;i<=n;i++){ 544 v[i].resize(m); 545 for(int j=1;j<m;j++){ 546 scanf("%d",&v[i][j]); 547 } 548 } 549 for(int i=1;i<n;i++){ 550 for(int j=1;j<m;j++){ 551 s[idx(i,j)]=1ll*w[i][j]-1ll*w[i][j+1]+1ll*v[i][j]-1ll*v[i+1][j]; 552 } 553 } 554 for(int i=1;i<n;i++){ 555 scanf("\n"); 556 for(int j=1;j<=m;j++){ 557 char p; 558 scanf("%c",&p); 559 if(p=='0'){ 560 merge(idx(i,j-1),idx(i,j)); 561 } 562 } 563 } 564 for(int i=1;i<=n;i++){ 565 scanf("\n"); 566 for(int j=1;j<m;j++){ 567 char q; 568 scanf("%c",&q); 569 if(q=='0'){ 570 merge(idx(i-1,j),idx(i,j)); 571 } 572 } 573 } 574 for(int i=1;i<=(n-1)*(m-1);i++){ 575 if(find(i)!=i&&find(i)!=find(0)){ 576 s[find(i)]+=s[i]; 577 } 578 } 579 for(int i=1;i<=(n-1)*(m-1);i++){ 580 if(find(i)==i&&find(i)!=find(0)){ 581 ans+=max(s[i],0ll); 582 } 583 } 584 printf("%lld\n",ans); 585 } 586 return 0; 587 } 588 ``` 589 590 #### [2205G — Simons and Diophantus Equation](https://codeforces.com/contest/2205/problem/G) 591 592 **Rate the problem!** 593 594 * Horrible problem 595 * Bad problem 596 * Average problem 597 * Good problem 598 * Epic problem 599 * Did not solve 600 601 Author: [Leftist_G](/profile/Leftist_G "Master Leftist_G") 602 603 Solution: [cool_milo](/profile/cool_milo "Master cool_milo"), [LiHn](/profile/LiHn "Master LiHn"), [liuhangxin](/profile/liuhangxin "International Master liuhangxin"), [Leftist_G](/profile/Leftist_G "Master Leftist_G") 604 605 **Hint 1** 606 607 The equation has an integral solution if and only if $\gcd(i\oplus j,j\oplus k)$ is a divisor of $n$. This is a famous theorem, called [Bézout's theorem](https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity). 608 609 **Hint 2** 610 611 Considering enumerating $g=\gcd(i\oplus j,j\oplus k)$, then we calculate how many tuples $(i,j,k)$ can exactly get this $g$. 612 613 **Hint 3** 614 615 Consider [Möbius inversion formula](https://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula). There is a famous equation that $[n=1]=\sum\limits_{d|n}\mu (d)$, where $\mu$ is the [Möbius function](https://en.wikipedia.org/wiki/M%C3%B6bius_function). 616 617 Apply Möbius' formula, and try to transform the formula we need to calculate until you have to calculate $f(T)$ for every $T$ from $1$ to $2m$, where $f(T)$ is the number of tuples $(i,j,k)$ such that $T$ is a divisor of both $i\oplus j$ and $j\oplus k$. 618 619 **Hint 4** 620 621 Consider enumerating $j$, $d_1T=i\oplus j$ and $d_2T=j\oplus k$. It's easy to see that the number of tuples $(j,d_1,d_2)$ is equal to the number of tuples $(i,j,k)$, if we ensure that $d_1T\oplus j \le m$ and $d_2T\oplus j\le m$. 622 623 **Hint 5** 624 625 Due to the series sum of [Harmonic series](https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)), it can be accepted to enumerate $T$ and $d_1$. 626 627 **Hint 6** 628 629 Observation: although a pair of $T$ and $d_1$ will process a set of $j$ such that $d_1T\oplus j\le m$, these $j$ will be distributed in $\mathcal O(\log m)$ intervals. 630 631 You can prove the observation by considering the bitmask of $m$ and $d_1T$. 632 633 **Hint 7** 634 635 The sum of the number of intervals will be $\mathcal O(m\ln m\log m)$. How about applying a data structure to record the intervals? 636 637 After recording, we can enumerate $d_2$ in the same complexity. It's easy to see we need to find the intersection of some intervals (the number of $j$ that satisfy both conditions simultaneously). We will make queries on our data structure to complete it. 638 639 **Hint 8** 640 641 [Trie](https://en.wikipedia.org/wiki/Trie) is a suitable data structure. If you are sensitive to some observations, [Fenwick Tree](https://en.wikipedia.org/wiki/Fenwick_tree) also works. 642 643 **Tutorial** 644 645 We will ignore a few corner cases, such as $i=j$ or $j=k$, and other corner cases involving $0$. The contributions of those cases are relatively simple or classical, so we omit them here; Consequently, some summation bounds below are not written with full formal tightness. 646 647 We actually want to compute 648 649 $ \sum\limits_{i=0}^m\sum\limits_{j=0}^m\sum\limits_{k=0}^m[\gcd(i\oplus j,j\oplus k)|n] $ 650 651 As usual, enumerate the value of the $\gcd$. Thus 652 653 $ \begin{aligned} =&\sum\limits_{d|n} \sum\limits_{i=0}^m\sum\limits_{j=0}^m\sum\limits_{k=0}^m[\gcd(i\oplus j,j\oplus k)=d]\\ =&\sum\limits_{d|n}\sum\limits_{p=i\oplus j}\sum\limits_{q=j\oplus k}[\gcd(p,q)=d]c(p,q) \end{aligned} $ 654 655 where $p=i\oplus j$, $q=j\oplus k$, and $c(p,q)$ is the number of tuples $(i,j,k)$ with those values of $p$ and $q$. 656 657 Apply Möbius inversion to the condition $\gcd(p,q)=d$: 658 659 $ \begin{aligned} =&\sum\limits_{d|n} \sum\limits_{d|p}\sum\limits_{d|q}[\gcd(\frac{p}{d},\frac{q}{d})=1]c(p,q)\\ =&\sum\limits_{d|n} \sum\limits_{d|p}\sum\limits_{d|q}\sum\limits_{d'|\frac{p}{d},d'|\frac{q}{d}}\mu(d')c(p,q)\\ \end{aligned} $ 660 661 where $\mu$ is the Möbius function. 662 663 We now change the summation order and pull $d'$ outward. 664 665 $ \begin{aligned} =&\sum\limits_{d|n}\sum\limits_{d'}^{\frac{2m}{d}}\mu(d')\sum\limits_{p}\sum\limits_{q}[dd'|p\land dd'|q]c(p,q)\\ \end{aligned} $ 666 667 Writing $T=dd'$ we obtain 668 669 $ \begin{aligned} =&\sum\limits_{T=1}^{2m}\sum\limits_{d|\gcd(n,T)}\mu(\frac{T}{d})\sum\limits_{p}\sum\limits_{q}[T|p\land T|q]c(p,q)\\ \end{aligned} $ 670 671 The outer sum over $T$ runs up to $2m$ because $p,q\in[0,2m]$. 672 673 The inner quantity depends on $T$ only. Let $f(T)$ be the number of tuples $(i,j,k)$ such that $T$ is a divisor of both $i\oplus j$ and $j\oplus k$. 674 675 Then the entire sum becomes 676 677 $ \begin{aligned} =&\sum\limits_{T=1}^{2m}\sum\limits_{d|\gcd(n,T)}\mu(\frac{T}{d})f(T)\\ \end{aligned} $ 678 679 Due to the series sum of the Harmonic series, we can enumerate $T$ and $d$ in $\mathcal O(m\ln m)$. Hence, the main task is to compute $f(T)$ efficiently for all $T$. 680 681 Fix $T$. We enumerate $j$ and count the number of pairs $(i,k)$ such that $i\oplus j$ and $j\oplus k$ are multiples of $T$. 682 683 Equivalently, we count the number of pairs $(d_1,d_2)$ under the enumerated $j$ such that 684 685 $ i\oplus j=d_1T, j\oplus k=d_2T $ 686 687 with the additional constraints $d_1T\oplus j\le m$ and $d_2T\oplus j\le m$ (because $(i,k)$ must lie in $[0,m]$). 688 689 Equivalently, if we can enumerate $d_1,d_2$ to get $d_1T$ and $d_2T$, we only need to find the number of $j$ that satisfy both constraints. If we enumerate $d_1$ to find the set of $j$ and record it, we can enumerate $d_2$ similarly, and what we need to calculate is the size of the intersection of the two sets. 690 691 Consider enumerating $d_1$ to get $d_1T$, due to bitmask theory, the $j$ such that $d_1T\oplus j\le m$ will be distributed in $\mathcal O(\log m)$ intervals. 692 693 By using Segment Tree or Fenwick Tree naively, we will solve the problem in $\mathcal O(m\ln m\log^2 m)$, which is too slow to get accepted in the problem. 694 695 By [LiHn](/profile/LiHn "Master LiHn")'s observation, actually, we can apply a Trie instead of a Segment Tree to record the intervals, because each interval can be formed by a subtree in the Trie. This will allow us to avoid incurring a logarithmic cost to find intervals in data structures every time. 696 697 By [Leftist_G](/profile/Leftist_G "Master Leftist_G")'s observation, there are only two types of intervals, but one type of intervals has $\mathcal O(\log)$, and another has $\mathcal O(1)$. We can avoid using Segment Tree or Fenwick Tree in the former. 698 699 By [liuhangxin](/profile/liuhangxin "International Master liuhangxin")'s observation, we can avoid using any data structure. We can naively save the intervals, sort them, and then apply two pointers to calculate the intersection. Note that if we implement the method naively, the complexity will turn to $\mathcal O(m\ln m\log m\log\log m)$ (although it may be enough to get Accepted). He used a designed order and implmented carefully to ensure his complexity. 700 701 All solutions above can solve the problem in $\mathcal O(m\ln m\log m)$. 702 703 Note that some not-so-good solutions may apply `__int128` to avoid integer overflow. Don't forget to deal with corner cases. 704 705 **Code (C++)** 706 707 By [LiHn](/profile/LiHn "Master LiHn"). 708 709 ``` 710 #include<bits/stdc++.h> 711 #define rep1(i, a, b) for(int i = a; i <= b; ++i) 712 #define rep2(i, a, b) for(int i = a; i >= b; --i) 713 #define pii pair <int, int> 714 #define ft first 715 #define sd second 716 #define ll long long 717 #define pb push_back 718 #define gmax(a, b) a = max(a, b) 719 #define gmin(a, b) a = min(a, b) 720 #define all(a) a.begin(), a.end() 721 #define debug cout << "------------------\n" 722 const int N = (1 << 21) + 10; 723 using namespace std; 724 int tot, ch[N][2], cnt[N], sz[N], fa[N]; ll f[N], sum[N]; 725 int p[N], vis[N], miu[N]; 726 void solve() { 727 int n, m; cin >> n >> m; 728 // get miu 729 rep1(i, 0, tot) ch[i][0] = ch[i][1] = sz[i] = fa[i] = sum[i] = cnt[i] = 0; 730 731 miu[1] = 1; 732 tot = 0; 733 rep1(i, 2, 2 * m) vis[i] = 0; 734 rep1(i, 2, 2 * m) { 735 if(!vis[i]) p[++tot] = i, miu[i] = -1; 736 for(int j = 1; p[j] * i <= 2 * m && j <= tot; ++j) { 737 vis[i * p[j]] = 1; 738 if(i % p[j] == 0) break; 739 miu[i * p[j]] = -miu[i]; 740 } 741 } 742 743 // get trie 744 tot = 1; 745 rep1(i, 0, m) { 746 int nw = 1; 747 rep2(j, 19, 0) { 748 int &nxt = ch[nw][i >> j & 1]; 749 if(!nxt) nxt = ++tot, fa[nxt] = nw; 750 nw = nxt; 751 } 752 while(nw) ++sz[nw], nw = fa[nw]; 753 } 754 755 // get f(T) 756 rep1(T, 1, 2 * m) { 757 f[T] = 0; 758 rep1(d, 1, 2 * m / T) { 759 int nw = 1, bg = 0, v = (d * T) ^ m; 760 rep2(i, 19, 0) { 761 int x = v >> i & 1; 762 if(m >> i & 1) { 763 int u = ch[nw][x ^ 1]; 764 if(u) ++cnt[u], sum[u] += sz[u]; 765 } 766 if(!ch[nw][x]) {bg = i + 1; break;} 767 nw = ch[nw][x]; 768 } 769 ll num = 0; 770 if(!bg) ++cnt[nw], ++sum[nw], ++num; 771 rep1(i, bg, 19) { 772 nw = fa[nw]; 773 int x = v >> i & 1; 774 if(m >> i & 1) { 775 int u = ch[nw][x ^ 1]; 776 num += sz[u]; 777 } 778 sum[nw] += num; 779 } 780 } 781 rep1(d, 1, 2 * m / T) { 782 int nw = 1, v = (d * T) ^ m; 783 ll num = 0; 784 rep2(i, 19, 0) { 785 int x = v >> i & 1; 786 num += cnt[nw]; 787 if(m >> i & 1) { 788 int u = ch[nw][x ^ 1]; 789 if(u) f[T] += sum[u] + 1ll * num * sz[u]; 790 } 791 nw = ch[nw][x]; 792 if(!nw) break; 793 } 794 if(nw) f[T] += sum[nw] + 1ll * num * sz[nw]; 795 } 796 rep1(d, 1, 2 * m / T) { 797 int nw = 1, bg = 0, v = (d * T) ^ m; 798 rep2(i, 19, 0) { 799 int x = v >> i & 1; 800 int u = ch[nw][x ^ 1]; 801 cnt[nw] = sum[nw] = cnt[u] = sum[u] = 0; 802 nw = ch[nw][x]; 803 } 804 if(nw) cnt[nw] = sum[nw] = 0; 805 } 806 } 807 808 ll ans = 0; 809 rep1(d, 1, 2 * m) { 810 if(n % d) continue; 811 rep1(j, 1, 2 * m / d) { 812 ans += miu[j] * f[j * d]; 813 } 814 } 815 816 // get i == j or j == k 817 rep1(g, 1, 2 * m) { 818 if(n % g) continue; 819 int nw = 1, v = g ^ m; 820 rep2(i, 19, 0) { 821 int x = v >> i & 1; 822 if(m >> i & 1) { 823 int u = ch[nw][x ^ 1]; 824 ans += 2 * sz[u]; 825 } 826 nw = ch[nw][x]; if(!nw) break; 827 } 828 if(nw) ans += 2; 829 } 830 831 cout << ans << '\n'; 832 } 833 int main() { 834 int T = 1; cin >> T; 835 while(T--) solve(); 836 return 0; 837 } 838 ```