codeforces-scrape

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

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 ![](/predownloaded/80/d2/80d2b7b51279c5e4fa7d91afafa6b02c5eeb4ab5.png)
    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 ```