2034.md (44114B)
1 Source: https://codeforces.com/blog/entry/136579 2 3 ### 👋 Salam Codeforces! 4 5 Here are the step-by-step solutions. Hoping you enjoy them! 😊 6 7 The announcement blog is available [here](https://codeforces.com/blog/entry/136396) and you can also explore all blogs related to Rayan [here!](https://codeforces.com/rayan) 8 9 #### [2034A - King Keykhosrow's Mystery](/contest/2034/problem/A) 10 11 **Idea:** [ArshiaDadras](/profile/ArshiaDadras "Master ArshiaDadras") — **Preparation:** [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM") 12 13 **Solution** 14 15 * **Step 1:** Prove that for the minimum value of $m$, we must have $m \% a = m \% b = 0$. 16 * **Step 2:** To prove this, show that if $m \% a = m \% b = x \gt 0$, then $m-1$ will also satisfy the problem's requirements. 17 * **Step 3:** Since $m \ge \min(a , b)$, if $x \gt 0$, then $m \gt \min(a , b)$ must hold. Therefore, $m - 1 \ge \min(a , b)$ implies that $m-1$ satisfies the requirements. 18 * **Step 4:** Thus, $m$ must be divisible by both $a$ and $b$. The smallest such $m$ is $lcm(a, b)$ which can be calculated in $O(\log(\max(a, b)))$. 19 20 **Implementation** 21 22 ``` 23 #include <bits/stdc++.h> 24 25 using namespace std; 26 27 int main(){ 28 int tt; 29 cin >> tt; 30 while(tt--){ 31 int a, b; 32 cin >> a >> b; 33 cout << lcm(a , b) << endl; 34 } 35 } 36 ``` 37 38 #### [2034B - Rakhsh's Revival](/contest/2034/problem/B) 39 40 **Idea:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh") and [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM") — **Preparation:** [AmShZ](/profile/AmShZ "Grandmaster AmShZ") 41 42 **Solution** 43 44 We will solve the problem using the following approach: 45 46 * Start from the leftmost spot and move rightwards. 47 * Whenever a consecutive segment of $m$ weak spots (i.e., $0$'s) is found, apply Timar to a segment of length $k$, starting from the last index of the weak segment. 48 * Repeat this process until no segment of $m$ consecutive weak spots remains. 49 50 The key idea behind this solution is that whenever we encounter a block of $m$ consecutive $0$'s, we need to strengthen it. Since we can apply Timar to a segment of length $k$, the optimal strategy is always to apply Timar starting at the last index of the block of $m$ consecutive $0$'s. 51 52 **Correctness Proof:** 53 54 1. For any block of $m$ consecutive $0$'s, we must apply Timar to at least one index within this block. Hence, the strengthened segment of length $k$ must overlap with the block of weak spots. 55 2. Suppose an optimal solution exists where Timar is applied to a segment starting leftward within the block. Suppose we shift this segment one step to the right (closer to the end of the block). In that case, the solution remains valid and optimal since it covers all weak spots in the block while reducing unnecessary overlap with already-strengthened areas. 56 57 By always starting from the last index of a block of $m$ consecutive $0$'s, this greedy strategy ensures that Timar is used in the minimum number of applications, making it correct and efficient. 58 59 **Implementation** 60 61 ``` 62 # include <bits/stdc++.h> 63 64 using namespace std; 65 66 const int xn = 2e5 + 10; 67 68 int q, n, m, k, ps[xn]; 69 string s; 70 71 int main() { 72 cin >> q; 73 while (q --) { 74 cin >> n >> m >> k >> s; 75 fill(ps, ps + n, 0); 76 int ans = 0, cnt = 0, sum = 0; 77 for (int i = 0; i < n; ++ i) { 78 sum += ps[i]; 79 if (sum || s[i] == '1') cnt = 0; 80 else { 81 cnt++; 82 if (cnt == m) { 83 sum++, ans++, cnt = 0; 84 if (i + k < n) ps[i + k]--; 85 } 86 } 87 } 88 cout << ans << "\n"; 89 } 90 } 91 ``` 92 93 #### [2034C - Trapped in the Witch's Labyrinth](/contest/2034/problem/C) 94 95 **Idea:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh") — **Preparation:** [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM") 96 97 **Solution** 98 99 * If a cell has a fixed direction (i.e., it points to another cell), and following that direction leads outside the maze, it must eventually exit the maze. Such cells cannot be part of any loop. 100 * We can analyze the remaining cells once we identify cells that lead out of the maze. Any undirected cell or $?$ cell might either lead to the exit or form part of a loop. 101 * If all neighboring cells of a $?$ cell can eventually lead out of the maze, then this $?$ cell will also lead out of the maze. The state of such $?$ cells can be determined based on their surroundings. 102 * For any remaining cells (directed cells that do not lead out of the maze, or other $?$ cells that cannot be determined to lead to an exit), we can assign directions such that starting from those cells will eventually lead to a loop. These cells will form the loops. 103 * To find how many cells will eventually lead to a loop, we can use a Depth-First Search (DFS) on the reversed graph, where all directions are reversed. By performing DFS starting from the *"out-of-maze"* cells, we can identify all cells that are reachable from the outside and thus will eventually lead out of the maze. 104 * Count the number of cells that can reach the exit. Subtract this number from the total number of cells in the maze to determine how many are part of loops (i.e., cells that cannot reach the exit). 105 106 **Implementation** 107 108 ``` 109 #include <bits/stdc++.h> 110 111 using namespace std; 112 113 int main() 114 { 115 int tc; 116 cin >> tc; 117 while(tc--){ 118 int n, m; 119 cin >> n >> m; 120 string c[n+1]; 121 for(int i = 1 ; i <= n ; i++) cin >> c[i] , c[i] = "-" + c[i]; 122 vector<pair<int,int>> jda[n+2][m+2]; 123 for(int i = 1 ; i <= n ; i++){ 124 for(int j = 1 ; j <= m ; j++){ 125 if(c[i][j] == 'U') jda[i-1][j].push_back({i , j}); 126 if(c[i][j] == 'R') jda[i][j+1].push_back({i , j}); 127 if(c[i][j] == 'D') jda[i+1][j].push_back({i , j}); 128 if(c[i][j] == 'L') jda[i][j-1].push_back({i , j}); 129 } 130 } 131 int vis[n+2][m+2] = {}; 132 queue<pair<int,int>> q; 133 for(int j = 0 ; j <= m+1 ; j++) vis[0][j] = 1 , q.push({0 , j}); 134 for(int i = 1 ; i <= n+1 ; i++) vis[i][0] = 1 , q.push({i , 0}); 135 for(int j = 1 ; j <= m+1 ; j++) vis[n+1][j] = 1 , q.push({n+1 , j}); 136 for(int i = 1 ; i <= n ; i++) vis[i][m+1] = 1 , q.push({i , m+1}); 137 while(q.size()){ 138 auto [i , j] = q.front(); 139 q.pop(); 140 for(auto [a , b] : jda[i][j]){ 141 if(vis[a][b] == 0){ 142 vis[a][b] = 1; 143 q.push({a , b}); 144 } 145 } 146 } 147 for(int i = 1 ; i <= n ; i++){ 148 for(int j = 1 ; j <= m ; j++){ 149 if(c[i][j] == '?' and 150 vis[i-1][j] and vis[i][j+1] and vis[i+1][j] and vis[i][j-1]) vis[i][j] = 1; 151 } 152 } 153 int ans = n * m; 154 for(int i = 1 ; i <= n ; i++){ 155 for(int j = 1 ; j <= m ; j++){ 156 if(vis[i][j] == 1) ans -= 1; 157 } 158 } 159 cout << ans << endl; 160 } 161 return 0; 162 } 163 ``` 164 165 #### [2034D - Darius' Wisdom](/contest/2034/problem/D) 166 167 **Idea and Preparation:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh") 168 169 **Solution** 170 171 * **Step 1:** Using two moves, we can move an element to any arbitrary position in the array. Thus, we can place all $0$'s in their correct positions with at most $2 \min(count(0), count(1) + count(2))$ moves. 172 * **Step 2:** After placing all $0$'s, the rest of the array will contain only $1$'s and $2$'s. To sort this part of the array, we need at most $min(count(1), count(2))$ moves. 173 * **Step 3:** The first step takes at most $n$ moves, and the second step takes at most $\frac{n}{2}$ moves. However, it can be proven that the total number of moves is at most $\frac{8n}{7}$. 174 * **Step 4:** We can assume $count(0) \leq count(2)$ without loss of generality (Why?). So, the maximum number of moves are: 175 176 $2 \min(count(0), count(1)+count(2))+\min(count(1), count(2))$ $= 2 \cdot count(0) + \min(count(1), count(2))$ $\le count(0) + \max(count(1), count(2)) + \min(count(1), count(2))$ $=count(0)+count(1)+count(2)=n$ 177 178 **Better approach:** 179 180 * **Step 1:** Since we are allowed to perform $n$ moves, assign each index one *"move"* as its *"specified cost"*. 181 * **Step 2:** While there exists an index with a value of $0$ or $2$ that can be fixed with just one move, fix it using its assigned cost. 182 * **Step 3:** After fixing all $0$'s, $2$'s, and all $1$'s except one, the remaining array will have the following structure and we are now allowed to use $2x+1$ moves: 183 184 $2\ 2\ \dots\ 2\ (x\ \text{times})\ 1\ 0\ 0\ \dots\ 0\ (x\ \text{times}),$ 185 186 * **Step 4:** First, swap the $1$ with a random element (denote it as $r$). Then, for $2x-1$ moves, swap the index with the value $1$ with any index where the correct value must be placed, except $r$. Finally, swap $1$ and $r$. 187 188 **Implementation (first approach)** 189 190 ``` 191 #include <bits/stdc++.h> 192 193 using namespace std; 194 195 const int N = 200000; 196 int n, cnt[3], a[N]; 197 vector<int> vip[3][3]; // Value In Position 198 vector<pair<int, int>> swaps; 199 200 inline int Pos(int index) { 201 if(index < cnt[0]) 202 return 0; 203 else if(index < cnt[0]+cnt[1]) 204 return 1; 205 else 206 return 2; 207 } 208 209 inline void AddBack(int index) { 210 vip[a[index]][Pos(index)].push_back(index); 211 } 212 213 inline void RemoveBack(int index) { 214 vip[a[index]][Pos(index)].pop_back(); 215 } 216 217 inline void Swap(int i, int j) { 218 swaps.push_back({i, j}); 219 RemoveBack(i); 220 RemoveBack(j); 221 swap(a[i], a[j]); 222 AddBack(i); 223 AddBack(j); 224 } 225 226 inline void Fix(int x) { 227 while(!vip[1][x].empty() or !vip[2-x][x].empty()) { 228 if(vip[1][x].empty()) { 229 if(!vip[1][2-x].empty()) 230 Swap(vip[2-x][x].back(), vip[1][2-x].back()); 231 else 232 Swap(vip[2-x][x].back(), vip[1][1].back()); 233 } 234 if(!vip[x][1].empty()) 235 Swap(vip[1][x].back(), vip[x][1].back()); 236 else 237 Swap(vip[1][x].back(), vip[x][2-x].back()); 238 } 239 } 240 241 int main() 242 { 243 ios_base::sync_with_stdio(false), cin.tie(0); 244 int t; 245 cin >> t; 246 while (t--) { 247 cin >> n; 248 for(int i = 0; i < n; i++) 249 cin >> a[i], cnt[a[i]]++; 250 for(int i = 0; i < n; i++) 251 AddBack(i); 252 if(cnt[0] <= cnt[2]) { 253 Fix(0); 254 Fix(2); 255 } else { 256 Fix(2); 257 Fix(0); 258 } 259 cout << swaps.size() << endl; 260 for(auto [i, j]: swaps) 261 cout << i+1 << ' ' << j+1 << endl; 262 cnt[0] = cnt[1] = cnt[2] = 0; 263 for(int i = 0; i < 3; i++) 264 for(int j = 0; j < 3; j++) 265 vip[i][j].clear(); 266 swaps.clear(); 267 } 268 return 0; 269 } 270 ``` 271 272 **Implementation (second approach)** 273 274 ``` 275 // In the name of god 276 #include <bits/stdc++.h> 277 278 using namespace std; 279 280 const int N = 200000; 281 int n, cnt[3], a[N]; 282 vector<int> vip[3][3]; // Value In Position 283 vector<pair<int, int>> swaps; 284 285 inline int Pos(int index) { 286 if(index < cnt[0]) 287 return 0; 288 else if(index < cnt[0]+cnt[1]) 289 return 1; 290 else 291 return 2; 292 } 293 294 inline void AddBack(int index) { 295 vip[a[index]][Pos(index)].push_back(index); 296 } 297 298 inline void RemoveBack(int index) { 299 vip[a[index]][Pos(index)].pop_back(); 300 } 301 302 inline void Swap(int i, int j) { 303 swaps.push_back({i, j}); 304 RemoveBack(i); 305 RemoveBack(j); 306 swap(a[i], a[j]); 307 AddBack(i); 308 AddBack(j); 309 } 310 311 inline void Fix() { 312 bool change; 313 do { 314 change = false; 315 while ((!vip[1][0].empty()) && (!vip[0][1].empty())) 316 Swap(vip[1][0].back(), vip[0][1].back()), change = true; 317 while ((!vip[1][0].empty()) && (!vip[0][2].empty())) 318 Swap(vip[1][0].back(), vip[0][2-0].back()), change = true; 319 while ((!vip[1][2].empty()) && (!vip[2][1].empty())) 320 Swap(vip[1][2].back(), vip[2][1].back()), change = true; 321 while ((!vip[1][2].empty()) && (!vip[2][0].empty())) 322 Swap(vip[1][2].back(), vip[2][0].back()), change = true; 323 } while (change); 324 } 325 326 inline void PingPong() { 327 if(vip[0][2].empty()) 328 return; 329 Swap(vip[1][1].back(), vip[0][2].back()); 330 while (true){ 331 Swap(vip[1][2].back(), vip[2][0].back()); 332 if(vip[0][2].empty()) 333 break; 334 Swap(vip[1][0].back(), vip[0][2].back()); 335 } 336 Swap(vip[1][0].back(), vip[0][1].back()); 337 } 338 339 int main() 340 { 341 ios_base::sync_with_stdio(false), cin.tie(0); 342 int t; 343 cin >> t; 344 while (t--) { 345 cin >> n; 346 for(int i = 0; i < n; i++) 347 cin >> a[i], cnt[a[i]]++; 348 for(int i = 0; i < n; i++) 349 AddBack(i); 350 Fix(); 351 PingPong(); 352 cout << swaps.size() << endl; 353 for(auto [i, j]: swaps) 354 cout << i+1 << ' ' << j+1 << endl; 355 // reset 356 cnt[0] = cnt[1] = cnt[2] = 0; 357 for(int i = 0; i < 3; i++) 358 for(int j = 0; j < 3; j++) 359 vip[i][j].clear(); 360 swaps.clear(); 361 } 362 return 0; 363 } 364 ``` 365 366 #### [2034E - Permutations Harmony](/contest/2034/problem/E) 367 368 **Idea:** [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM") and [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh") — **Preparation:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh") 369 370 **Solution** 371 372 * **Step 1:** There are $n$ positions that must be equal, and their sum is $\frac{n \cdot (n+1) \cdot k}{2}$. Hence, each position must be $\frac{(n+1) \cdot k}{2}$. Additionally, there must be $k$ distinct permutations, so $k \leq n!$. 373 * **Step 2:** For even $k$, we can group $n!$ permutations into $\frac{n!}{2}$ double handles, where each group corresponds to a solution for $k = 2$. Then, pick $\frac{k}{2}$ handles. The match for permutation $a_1, a_2, \ldots, a_n$ is $(n+1)-a_1, (n+1)-a_2, \ldots, (n+1)-a_n$. 374 * **Step 3:** For $k = 1$, $n$ must be $1$. Symmetrically, $k$ cannot be $n! - 1$. Solutions for other odd $k$ will now be provided. 375 * **Step 4:** To construct an answer for $k = 3$ and $n = 2x + 1$, consider the following derived using a greedy approach: 376 377 | $p_1$ | $p_2$ | $p_3$ | $p_4$ | $p_5$ | $ \ldots $ | $p_{2x-1} $ | $ p_{2x} $ | $ p_{2x+1} $ | 378 | --- | --- | --- | --- | --- | --- | --- | --- | --- | 379 | 1 | 2 | 3 | 4 | 5 | $ \ldots $ | $ 2x-1 $ | $ 2x $ | $ 2x+1 $ | 380 | $ x+1 $ | $ 2x+1 $ | $ x $ | $ 2x $ | $ x-1 $ | $ \ldots $ | 2 | $ x+2 $ | 1 | 381 | $ 2x+1 $ | $ x $ | $ 2x $ | $ x-1 $ | $ 2x-1 $ | $ \ldots $ | $ x+2 $ | 1 | $ x+1 $ | 382 383 * **Step 5:** Now, combine the solution for even $k$ and the $k = 3$ solution by selecting the 3 permutations and $\frac{k-3}{2}$ other handles. 384 385 **Implementation** 386 387 ``` 388 // In the name of God 389 #include <bits/stdc++.h> 390 using namespace std; 391 392 int main() { 393 ios_base::sync_with_stdio(false), cin.tie(0); 394 int t; 395 cin >> t; 396 int f[8] = {1,1,2,6,24,120,720,5040}; 397 while(t--) { 398 int n, k; 399 cin >> n >> k; 400 if(min(n, k) == 1) { 401 if(n*k == 1) { 402 cout << "Yes\n1\n"; 403 } else cout << "No\n"; 404 } else if(n < 8 and (f[n] < k or f[n] == k+1)) { 405 cout << "No\n"; 406 } else if(n % 2 == 0 and k % 2 == 1) { 407 cout << "No\n"; 408 } else { 409 vector<vector<int>> base, all; 410 vector<int> per(n); 411 for(int i = 0; i < n; i++) per[i] = i+1; 412 if(k % 2) { 413 vector<int> p1(n), p2(n); 414 for(int i = 0; i < n; i += 2) p1[i] = (n+1)/2-i/2, p2[i] = n-i/2; 415 for(int i = 1; i < n; i += 2) p1[i] = n-i/2, p2[i] = n/2-i/2; 416 all = base = {per, p1, p2}; 417 k -= 3; 418 } 419 do { 420 if(k == 0) 421 break; 422 vector<int> mirror(n); 423 for(int i = 0; i < n; i++) 424 mirror[i] = n+1-per[i]; 425 if(per < mirror) { 426 bool used = false; 427 for(auto &p: base) used |= (p == per), used |= (p == mirror); 428 if(not used) { 429 k -= 2; 430 all.push_back(per); 431 all.push_back(mirror); 432 } 433 } 434 } while (next_permutation(per.begin(), per.end())); 435 cout << "Yes\n"; 436 for(auto p: all) { 437 for(int i = 0; i < n; i++) 438 cout << p[i] << (i+1==n?'\n':' '); 439 } 440 } 441 } 442 443 return 0; 444 } 445 446 // Thanks God 447 ``` 448 449 #### [2034F1 - Khayyam's Royal Decree (Easy Version)](/contest/2034/problem/F1) 450 451 **Idea and Preparation:** [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 452 453 **Solution** 454 455 * **Step 1:** For simplicity, redefine the special conditions for the number of rubies and sapphires in your satchel (not chest). Add two dummy states, $(0,0)$ and $(n,m)$ for convenience (the first one indexed as $0$ and the second one indexed as $k+1$). Note that these dummy states won’t involve doubling the value. 456 * **Step 2:** Order the redefined conditions $(x, y)$ in increasing order based on the value of $x + y$. 457 * **Step 3:** Define $ways_{i,j}$ as the number of ways to move from state $i$ to state $j$ without passing through any other special condition. This can be computed using inclusion-exclusion in $O(k^3)$. 458 * **Step 4:** Define $cost_{i,j}$, the increase in value for moving directly from state $i$ to state $j$ without intermediate doubling, as: 459 460 $cost_{i,j} = 2|x_i - x_j| + |y_i - y_j|$ 461 462 * **Step 5:** Define $dp_i$ as the total sum of the value of your satchel across all ways to reach the state defined by the $i$-th condition. This can be computed recursively as: 463 464 $dp_i = 2 \sum_{0 \leq j \lt i} ways_{j,i} \times (dp_j + \binom{x_j + y_j}{x_j} \times cost_{j,i})$ 465 466 * **Step 6:** Compute the final answer as the value of $dp_{k+1}$ divided by the total number of ways to move from $(0,0)$ to $(n,m)$, which is $\binom{n+m}{n}$. 467 468 **Implementation** 469 470 ``` 471 #include <bits/stdc++.h> 472 using namespace std; 473 474 #define nl "\n" 475 #define nf endl 476 #define ll long long 477 #define pb push_back 478 #define _ << ' ' << 479 480 #define INF (ll)1e18 481 #define mod 998244353 482 #define maxn 400010 483 484 ll fc[maxn], nv[maxn]; 485 486 ll fxp(ll b, ll e) { 487 ll r = 1, k = b; 488 while (e != 0) { 489 if (e % 2) r = (r * k) % mod; 490 k = (k * k) % mod; e /= 2; 491 } 492 return r; 493 } 494 495 ll inv(ll x) { 496 return fxp(x, mod - 2); 497 } 498 499 ll bnm(ll a, ll b) { 500 if (a < b || b < 0) return 0; 501 ll r = (fc[a] * nv[b]) % mod; 502 r = (r * nv[a - b]) % mod; 503 return r; 504 } 505 506 int main() { 507 ios::sync_with_stdio(0); 508 cin.tie(0); 509 510 fc[0] = 1; nv[0] = 1; 511 for (ll i = 1; i < maxn; i++) { 512 fc[i] = (i * fc[i - 1]) % mod; nv[i] = inv(fc[i]); 513 } 514 515 ll t; cin >> t; 516 while (t--) { 517 ll n, m, k; cin >> n >> m >> k; 518 vector<array<ll, 2>> a(k + 2, {0, 0}); 519 for (ll i = 1; i <= k; i++) { 520 cin >> a[i][0] >> a[i][1]; 521 a[i][0] = n - a[i][0]; a[i][1] = m - a[i][1]; 522 } 523 a[k + 1] = {n, m}; k++; 524 sort(a.begin() + 1, a.end()); 525 526 auto paths = [&](ll i, ll j) { 527 ll dx = a[j][0] - a[i][0], dy = a[j][1] - a[i][1]; 528 return bnm(dx + dy, dx); 529 }; 530 531 auto add = [&](ll &x, ll y) { 532 x = (x + y) % mod; 533 x = (x + mod) % mod; 534 }; 535 536 vector direct(k + 1, vector<ll>(k + 1, 0)); 537 for (ll i = 1; i <= k; i++) { 538 for (ll j = i - 1; j >= 0; j--) { 539 direct[j][i] = paths(j, i); 540 for (ll l = j + 1; l < i; l++) { 541 add(direct[j][i], -paths(j, l) * direct[l][i]); 542 } 543 } 544 } 545 546 vector<ll> dp(k + 1, 0); 547 for (ll i = 1; i <= k; i++) { 548 for (ll j = 0; j < i; j++) { 549 if (direct[j][i] == 0) continue; 550 ll partial = dp[j]; 551 ll delta = 2 * (a[i][0] - a[j][0]) + (a[i][1] - a[j][1]); 552 add(partial, paths(0, j) * delta); 553 add(dp[i], partial * direct[j][i]); 554 } 555 if (i != k) dp[i] = (2 * dp[i]) % mod; 556 } 557 558 ll ans = (dp[k] * inv(bnm(n + m, m))) % mod; 559 cout << ans << nl; 560 } 561 562 return 0; 563 } 564 ``` 565 566 #### [2034F2 - Khayyam's Royal Decree (Hard Version)](/contest/2034/problem/F2) 567 568 **Idea and Preparation:** [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 569 570 **Solution** 571 572 * **Step 1:** For simplicity, redefine the special conditions for the number of rubies and sapphires in your satchel (not chest). 573 * **Step 2:** Order the redefined conditions $(x, y)$ in increasing order based on the value of $x + y$. 574 * **Step 3:** Define $total_{i,j}$ as the total number of ways to move from state $i$ to state $j$ (ignoring special condition constraints). This can be computed as: 575 576 $total_{i,j} = \binom{|x_i - x_j| + |y_i - y_j|}{|x_i - x_j|}$ 577 578 * **Step 4:** Define $weight_i$ as the total contribution of all paths passing through condition $i$ to reach the final state $(n, m)$. This can be computed recursively as: 579 580 $weight_i = \sum_{i \lt j \leq k} total_{i,j} \times weight_j$ 581 582 * **Step 5:** The main insight is to account for the doubling effect of passing through multiple scrolls. If a path passes through a sequence of conditions $s_1, \dots, s_c$, each gem collected before entering $s_1$ is counted with multiplicity $2^c$. Instead of explicitly multiplying by $2^c$, consider the number of subsets $q_1, \dots, q_d$ of $s_1, \dots, s_c$. By summing over all subsets, the correct multiplicity is automatically handled. 583 * **Step 6:** Define $dp_i$ as the total value of all paths passing through condition $i$, considering the contribution of each state’s rubies and sapphires. This can be computed as: 584 585 $dp_i = (2x_i + y_i) \times total_{0, i} \times weight_i$ 586 587 * **Step 7:** Compute the final answer as $\sum dp_i$ divided by the total number of ways to move from $(0,0)$ to $(n,m)$, which is equal to $\binom{n+m}{n}$. 588 589 **Clarification:** The approach hinges on the insight that $2^i$ can be derived from the structure of subsets of scrolls $s_1, \dots, s_c$. Generalizations to $3^i$ or other multiplicative factors are possible by appropriately modifying $weight_i$ and adjusting the factor in Step 5. For example, a factor of 3 can be applied by multiplying path contributions by 2 at the relevant steps. 590 591 **Implementation** 592 593 ``` 594 #include <bits/stdc++.h> 595 using namespace std; 596 597 #define nl "\n" 598 #define nf endl 599 #define ll long long 600 #define pb push_back 601 #define _ << ' ' << 602 603 #define INF (ll)1e18 604 #define mod 998244353 605 #define maxn 400010 606 607 ll fc[maxn], nv[maxn]; 608 609 ll fxp(ll b, ll e) { 610 ll r = 1, k = b; 611 while (e != 0) { 612 if (e % 2) r = (r * k) % mod; 613 k = (k * k) % mod; e /= 2; 614 } 615 return r; 616 } 617 618 ll inv(ll x) { 619 return fxp(x, mod - 2); 620 } 621 622 ll bnm(ll a, ll b) { 623 if (a < b || b < 0) return 0; 624 ll r = (fc[a] * nv[b]) % mod; 625 r = (r * nv[a - b]) % mod; 626 return r; 627 } 628 629 int main() { 630 ios::sync_with_stdio(0); 631 cin.tie(0); 632 633 fc[0] = 1; nv[0] = 1; 634 for (ll i = 1; i < maxn; i++) { 635 fc[i] = (i * fc[i - 1]) % mod; nv[i] = inv(fc[i]); 636 } 637 638 ll t; cin >> t; 639 while (t--) { 640 ll n, m, k; cin >> n >> m >> k; 641 vector<array<ll, 2>> a(k + 2, {0, 0}); 642 for (ll i = 1; i <= k; i++) { 643 cin >> a[i][0] >> a[i][1]; 644 a[i][0] = n - a[i][0]; a[i][1] = m - a[i][1]; 645 } 646 a[k + 1] = {n, m}; k++; 647 sort(a.begin() + 1, a.end()); 648 649 auto paths = [&](ll i, ll j) { 650 ll dx = a[j][0] - a[i][0], dy = a[j][1] - a[i][1]; 651 return bnm(dx + dy, dx); 652 }; 653 654 auto add = [&](ll &x, ll y) { 655 x = (x + y) % mod; 656 x = (x + mod) % mod; 657 }; 658 659 vector<ll> cnt_weighted(k + 1, 0); 660 cnt_weighted[k] = 1; 661 for (ll i = k - 1; i >= 1; i--) { 662 for (ll j = i + 1; j <= k; j++) { 663 add(cnt_weighted[i], paths(i, j) * cnt_weighted[j]); 664 } 665 } 666 667 ll ans = 0; 668 for (ll i = 1; i <= k; i++) { 669 ll delta = 2 * a[i][0] + a[i][1]; 670 add(ans, delta * paths(0, i) % mod * cnt_weighted[i]); 671 } 672 673 ans = (ans * inv(bnm(n + m, m))) % mod; 674 cout << ans << nl; 675 } 676 677 return 0; 678 } 679 ``` 680 681 **Note:** Thanks to [peti1234](/profile/peti1234 "Legendary Grandmaster peti1234") and [_istil](/profile/_istil "International Grandmaster _istil") for suggesting the idea of including this subtask! 682 683 #### [2034G1 - Simurgh's Watch (Easy Version)](/contest/2034/problem/G1) 684 685 **Idea:** [ArshiaDadras](/profile/ArshiaDadras "Master ArshiaDadras") — **Preparation:** [AmShZ](/profile/AmShZ "Grandmaster AmShZ") and [ArshiaDadras](/profile/ArshiaDadras "Master ArshiaDadras") 686 687 **Solution** 688 689 * It is easy to check if the solution can be achieved with only one color. For any time point $x$, there must be at most one interval containing $x$, since if multiple intervals contain $x$, they must be colored differently. 690 * A simple strategy is to solve the problem using three colors. First, we color some intervals with colors 1 and 2, then color others with color 3. 691 + For each step, we find the leftmost point that has not been colored yet and color the segment that contains this point. 692 + We always choose the interval with the largest endpoint that contains the current point. 693 + By coloring the intervals alternately with colors 1 and 2, we ensure that all points are covered by exactly one of these colors. 694 * Now, we check if we can color the intervals with just two colors using a greedy algorithm: 695 + We iterate over the intervals sorted by start (increasingly) and then by end (decreasingly). 696 + At each point, we keep track of the number of colors used in previous intervals that are not yet closed. Let this number be $I$, and suppose we are currently at interval $i$. 697 + We color the current interval based on the value of $I$: 698 - If $I = 0$, color interval $i$ with color 1. 699 - If $I = 1$, color interval $i$ with the opposite color of the current used color. 700 - If $I = 2$, color interval $i$ with the same color of the interval with the smallest endpoint among the currently open intervals. 701 + If it is impossible to assign a unique color between overlapping intervals at any point, it can be shown that coloring the intervals using only 2 colors is impossible. 702 703 **Solving G1 using G2:** 704 705 * It’s sufficient to check the integer points and half-points (e.g., 1.5, 2.5, …) to verify whether the coloring is valid (Why?). 706 * To handle this, we can multiply all the given points by two, effectively converting the problem into one in which only integer points exist. 707 * After this transformation, we solve the problem in the integer system of G2, where the intervals and coloring rules are defined using integer boundaries! 708 709 **Note:** A brief explanation of why this greedy algorithm works can be found [here](https://codeforces.com/blog/entry/136579?#comment-1223389). 710 711 **Implementation** 712 713 ``` 714 /* In the name of Allah */ 715 // Welcome to the Soldier Side! 716 // Where there's no one here, but me... 717 #include<bits/stdc++.h> 718 using namespace std; 719 720 const int N = 2e5 + 5; 721 int t, n, l[N], r[N], col[N]; 722 vector<int> st[N << 1], en[N << 1]; 723 724 void compress_points() { 725 vector<int> help; 726 for (int i = 0; i < n; i++) { 727 help.push_back(l[i]); 728 help.push_back(r[i]); 729 } 730 731 sort(help.begin(), help.end()); 732 help.resize(unique(help.begin(), help.end()) - help.begin()); 733 for (int i = 0; i < n; i++) { 734 l[i] = lower_bound(help.begin(), help.end(), l[i]) - help.begin(); 735 r[i] = lower_bound(help.begin(), help.end(), r[i]) - help.begin(); 736 } 737 } 738 739 void record_points() { 740 for (int i = 0; i < n; i++) { 741 st[l[i]].push_back(i); 742 en[r[i] + 1].push_back(i); 743 } 744 for (int i = 0; i < 2 * n; i++) 745 sort(st[i].begin(), st[i].end(), [](int i, int j) { 746 return r[i] > r[j]; 747 }); 748 } 749 750 void try3_points() { 751 fill(col, col + n, 0); 752 int cur = -1, nxt = -1, c = 2; 753 for (int i = 0; i < 2 * n; i++) { 754 if (st[i].empty()) 755 continue; 756 757 if (!~cur || i > r[cur]) { 758 if (cur ^ nxt && r[nxt] < i) { 759 col[nxt] = (c ^= 3); 760 cur = nxt; 761 } 762 763 if (cur ^ nxt) 764 cur = nxt; 765 else { 766 cur = st[i][0]; 767 for (int p: st[i]) 768 if (r[p] > r[cur]) 769 cur = p; 770 nxt = cur; 771 } 772 col[cur] = (c ^= 3); 773 } 774 775 for (int p: st[i]) 776 if (r[p] > r[nxt]) 777 nxt = p; 778 } 779 if (cur ^ nxt) 780 col[nxt] = c ^ 3; 781 } 782 783 bool is_bad(set<pair<int, int>> s[2]) { 784 int cnt1 = s[0].size(), cnt2 = s[1].size(); 785 return cnt1 + cnt2 && cnt1 ^ 1 && cnt2 ^ 1; 786 } 787 788 void try2_points() { 789 set<pair<int, int>> s[2]; 790 for (int i = 0; i <= 2 * n; i++) { 791 for (int p: en[i]) 792 s[col[p]].erase({r[p], p}); 793 if (is_bad(s)) { 794 try3_points(); 795 return; 796 } 797 798 for (int p: st[i]) { 799 int cnt1 = s[0].size(); 800 int cnt2 = s[1].size(); 801 if (!cnt1 || !cnt2) 802 col[p] = cnt1 > 0; 803 else if (cnt1 ^ cnt2) 804 col[p] = cnt1 < cnt2; 805 else 806 col[p] = s[0].begin()->first > s[1].begin()->first; 807 808 s[col[p]].insert({r[p], p}); 809 if (is_bad(s)) { 810 try3_points(); 811 return; 812 } 813 } 814 } 815 } 816 817 void read_input() { 818 cin >> n; 819 for (int i = 0; i < n; i++) 820 cin >> l[i] >> r[i]; 821 } 822 823 void solve() { 824 compress_points(); 825 record_points(); 826 try2_points(); 827 } 828 829 void write_output() { 830 cout << *max_element(col, col + n) + 1 << endl; 831 for (int i = 0; i < n; i++) 832 cout << col[i] + 1 << "\n "[i < n - 1]; 833 } 834 835 void reset_variables() { 836 for (int i = 0; i < n; i++) { 837 col[i] = 0; 838 st[l[i]].clear(); 839 en[r[i] + 1].clear(); 840 } 841 } 842 843 int main() { 844 ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0); 845 for (cin >> t; t--; reset_variables()) 846 read_input(), solve(), write_output(); 847 return 0; 848 } 849 ``` 850 851 **Note:** Special thanks to **Prof. Mohammad Ali Abam** for proposing this problem! 852 853 **Fun fact:** He wasn’t able to solve it himself, but when he presented it to me (Arshia is talking...), he said, *“I don’t know how to solve it yet, but I guess its difficulty would be at most around E…”* 854 855 #### [2034G2 - Simurgh's Watch (Hard Version)](/contest/2034/problem/G2) 856 857 **Idea and Preparation:** [ArshiaDadras](/profile/ArshiaDadras "Master ArshiaDadras") 858 859 **Solution** 860 861 * **Step 1:** It is easy to check if the solution can be achieved with only one color. For any time point $x$, there must be at most one interval containing $x$, since if multiple intervals contain $x$, they must be colored differently. 862 * **Step 2:** A simple strategy is to solve the problem using three colors; First, we color some intervals with colors 1 and 2, then color others with color 3. For each step, we find the leftmost point that has not been colored yet and color the segment that contains this point. We always choose the interval with the largest endpoint that contains the current point. By coloring the intervals alternately with colors 1 and 2, we ensure that all points are covered by exactly one of these colors. 863 * **Step 3:** Now, we check if we can color the intervals with just two colors. For some point, $x$, suppose we have already colored the intervals $[l_i, r_i]$ with $l_i \leq x$, such that all points before $x$ have a unique color. At each step, we only need to determine which of the intervals like $p$ that $l_p \leq x \leq r_p$ can have a unique color. The key observation is that if an interval can be uniquely colored at time $x$, it can also remain uniquely colored for all times $t$ such that $x \leq t \leq r_i$. 864 + **Lemma:** If an interval $[l_i, r_i]$ can be uniquely colored at time $x$, it can also be uniquely colored at all subsequent times $x \leq t \leq r_i$. 865 + **Proof:** Consider coloring the intervals at time $x$. Intervals starting at $x + 1$ will be colored with the opposite color to interval $i$, ensuring that the interval remains uniquely colored at time $x+1$. 866 + With this lemma, we can conclude that the changes in the coloring are $O(n)$. It suffices to track the intervals that are added and removed at each point in time. 867 * **Step 4:** To efficiently move from time $x$ to $x + 1$, we perform the following steps: 868 + Remove the intervals that have $r_i = x$ (since they no longer contain $x+1$). 869 + Add the intervals that have $l_i = x + 1$. 870 + Update the set of intervals that can be uniquely colored at time $x+1$. 871 * **Step 5:** Finally, we observe that only the following points are important for the coloring: 872 873 + $l_i$ and $r_i$ for each interval. 874 + $l_i - 1$ and $r_i + 1$, since these points mark the boundaries where intervals start or end. 875 876 Thus, we can compress the numbers to reduce the range of values we need to process. 877 878 **Implementation** 879 880 ``` 881 /* In the name of Allah */ 882 // Welcome to the Soldier Side! 883 // Where there's no one here, but me... 884 #include<bits/stdc++.h> 885 using namespace std; 886 887 const int N = 2e5 + 5; 888 vector<int> st[N << 2], en[N << 2]; 889 int t, n, k, l[N], r[N], dp[N], col[N], prv[N]; 890 891 void compress_numbers() { 892 vector<int> help; 893 for (int i = 0; i < n; i++) { 894 help.push_back(l[i] - 1); 895 help.push_back(l[i]); 896 help.push_back(r[i]); 897 help.push_back(r[i] + 1); 898 } 899 900 sort(help.begin(), help.end()); 901 help.resize(k = unique(help.begin(), help.end()) - help.begin()); 902 for (int i = 0; i < n; i++) { 903 l[i] = lower_bound(help.begin(), help.end(), l[i]) - help.begin(); 904 r[i] = lower_bound(help.begin(), help.end(), r[i]) - help.begin(); 905 } 906 } 907 908 void save_checkpoints() { 909 for (int i = 0; i < n; i++) { 910 st[l[i]].push_back(i); 911 en[r[i]].push_back(i); 912 } 913 } 914 915 bool check_one() { 916 for (int i = 0, open = 0; i < k; i++) { 917 open += st[i].size(); 918 if (open > 1) 919 return false; 920 open -= en[i].size(); 921 } 922 return true; 923 } 924 925 void color_with_two() { 926 for (int i = k - 1, cur = -1; ~i; i--) { 927 if (en[i].empty()) 928 continue; 929 930 while (!~cur || i < dp[cur]) 931 if (~cur && ~prv[cur]) { 932 col[prv[cur]] = col[cur]; 933 if (r[prv[cur]] >= l[cur]) 934 col[prv[cur]] ^= 1; 935 cur = prv[cur]; 936 } 937 else 938 for (int p: en[i]) 939 if (~dp[p] && (!~cur || dp[p] < dp[cur])) 940 cur = p; 941 942 for (int p: en[i]) 943 if (p ^ cur) 944 col[p] = col[cur] ^ 1; 945 } 946 } 947 948 bool check_two() { 949 set<int> goods, bads; 950 fill(dp, dp + n, -1); 951 fill(prv, prv + n, -1); 952 for (int i = 0; i < k; i++) { 953 int prev = -1; 954 if (i) 955 for (int p: en[i - 1]) { 956 bads.erase(p), goods.erase(p); 957 if (~dp[p] && (!~prev || dp[p] < dp[prev])) 958 prev = p; 959 } 960 int open = goods.size() + bads.size(); 961 962 if (open == 1 || (open == 2 && !goods.empty())) { 963 for (int p: bads) { 964 if (open == 1) 965 prv[p] = prev; 966 else 967 prv[p] = *goods.begin(); 968 goods.insert(p); 969 dp[p] = i; 970 } 971 bads.clear(); 972 } 973 974 if (open == 1) 975 prev = *goods.begin(); 976 for (int p: st[i]) 977 if (!open || open == 1 || ~prev) { 978 goods.insert(p); 979 prv[p] = prev; 980 dp[p] = i; 981 } 982 else 983 bads.insert(p); 984 open += st[i].size(); 985 986 if (open && goods.empty()) 987 return false; 988 } 989 990 color_with_two(); 991 return true; 992 } 993 994 void color_with_three() { 995 int cur = -1, nxt = -1; 996 for (int i = 0; i < k; i++) { 997 if (st[i].empty()) 998 continue; 999 1000 if (~cur && i > r[cur] && nxt ^ cur) { 1001 col[nxt] = col[cur] ^ 3; 1002 cur = nxt; 1003 } 1004 if (!~cur || i > r[cur]) { 1005 for (int p: st[i]) 1006 if (!~cur || r[p] > r[cur]) 1007 cur = p; 1008 col[nxt = cur] = 1; 1009 } 1010 1011 for (int p: st[i]) 1012 if (r[p] > r[nxt]) 1013 nxt = p; 1014 } 1015 1016 if (cur ^ nxt) 1017 col[nxt] = col[cur] ^ 3; 1018 } 1019 1020 void read_input() { 1021 cin >> n; 1022 for (int i = 0; i < n; i++) 1023 cin >> l[i] >> r[i]; 1024 } 1025 1026 void solve() { 1027 compress_numbers(); 1028 save_checkpoints(); 1029 if (check_one()) 1030 return; 1031 if (check_two()) 1032 return; 1033 color_with_three(); 1034 } 1035 1036 void write_output() { 1037 cout << *max_element(col, col + n) + 1 << endl; 1038 for (int i = 0; i < n; i++) 1039 cout << col[i] + 1 << "\n "[i < n - 1]; 1040 } 1041 1042 void reset_variables() { 1043 fill(col, col + n, 0); 1044 for (int i = 0; i < k; i++) { 1045 st[i].clear(); 1046 en[i].clear(); 1047 } 1048 } 1049 1050 int main() { 1051 ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0); 1052 for (cin >> t; t--; reset_variables()) 1053 read_input(), solve(), write_output(); 1054 return 0; 1055 } 1056 ``` 1057 1058 **Note:** Thanks to [_istil](/profile/_istil "International Grandmaster _istil") and [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan") for suggesting the idea of including this subtask! 1059 1060 #### [2034H - Rayan vs. Rayaneh](/contest/2034/problem/H) 1061 1062 **Idea and Preparation:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh") 1063 1064 **Solution** 1065 1066 * **Step 1:** According to [Bézout's Identity](https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity), we can compute $\gcd(x_1, \ldots, x_t)$ and all its multipliers as an integer linear combination of $x_1, x_2, \ldots, x_t$. 1067 * **Step 2:** A set {$a_1, \ldots, a_k$} is good (integer linearly independent) if for every $i$, $\gcd(${$a_j \mid j \neq i$}$) \nmid a_i$. 1068 * **Step 3:** A set {$a_1, \ldots, a_k$} is good if and only if there exists a set {${p_1}^{q_1}, {p_2}^{q_2}, \ldots, {p_k}^{q_k}$} such that ${p_i}^{q_i} \mid a_j$ for $j \neq i$ and ${p_i}^{q_i} \nmid a_i$. 1069 * **Step 4:** The set {$a_1, \ldots, a_k$} can be identified by determining {${p_1}^{q_1}, {p_2}^{q_2}, \ldots, {p_k}^{q_k}$}. Assume $p_1^{q_1} \lt p_2^{q_2} \lt \ldots \lt p_k^{q_k}$, where $p_i \neq p_j$ and $p_i$ is prime. 1070 * **Step 5:** Let $G = {p_1}^{q_1} \cdot {p_2}^{q_2} \ldots \cdot {p_k}^{q_k}.$ Then {$a_1, \ldots, a_k$} is good if and only if $\frac{G}{{p_i}^{q_i}} \mid a_i$ and $G \nmid a_i$ for every $i$. 1071 * **Step 6:** The answer is a singleton if, for every pair of numbers $x$ and $y$ in the array, $x \mid y$ or $y \mid x$. Since the numbers are distinct, a good subset {$a_1, a_2$} can always be found by searching the first $\log M + 2$ elements. 1072 * **Step 7:** Define $CM[i]$ (count multipliers of $i$) as the number of $x$ such that $i \mid a_x$. This can be computed in $O(n + M \log M)$. 1073 * **Step 8:** A corresponding set {$a_1, \ldots, a_k$} exists for a set {${p_1}^{q_1}, {p_2}^{q_2}, \ldots, {p_k}^{q_k}$} if and only if $CM\left[\frac{G}{{p_i}^{q_i}}\right] \gt CM[G] \geq 0$ for all $i$. 1074 * **Step 9:** Iterate over all valid sets of the form {${p_1}^{q_1}, {p_2}^{q_2}, \ldots, {p_k}^{q_k}$}, and check if a corresponding {$a_1, a_2, \ldots, a_k$} exists. Note that $k \geq 3$ since a good subset {$a_1, a_2$} is found using another method. 1075 * **Step 10:** We know $\frac{G}{{p_1}^{q_1}} \leq M$ and also ${p_1}^{q_1} \leq \sqrt{M},$ as ${p_1}^{q_1} \leq \sqrt{{p_2}^{q_2} \cdot {p_3}^{q_3}} \leq \sqrt{\frac{G}{{p_1}^{q_1}}} \leq \sqrt{M}.$ 1076 * **Step 11:** There are $\sum_{i=1}^{\frac{\log M}{2}} P[\lfloor \sqrt[2i]{M} \rfloor]$ numbers in the form ${p_1}^{q_1}$, where $P[i]$ denotes the number of primes in the range $[1, i]$. This count is $O(\frac{\sqrt M}{\log M})$. 1077 * **Step 12:** The value of $k$ is at most 6 (denoted as $K$), as ${p_2}^{q_2} \ldots {p_k}^{q_k} = \frac{G}{{p_1}^{q_1}} \leq M,$ and $3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \leq M \lt 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17.$ 1078 * **Step 13:** We can determine {$a_1, \ldots, a_k$} from {${p_1}^{q_1}, {p_2}^{q_2}, \ldots, {p_k}^{q_k}$} in $O(n \cdot K)$. 1079 1080 The total time complexity is $O\left(T \cdot M \cdot \frac{\sqrt M}{\log M} \cdot K + T \cdot M \cdot \log M + \sum_{i=0}^T n_i \cdot K\right).$ 1081 1082 **Implementation** 1083 1084 ``` 1085 /// In the name of God the most beneficent the most merciful 1086 1087 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") 1088 #include <bits/stdc++.h> 1089 using namespace std; 1090 typedef long long ll; 1091 1092 constexpr int T = 100; 1093 constexpr int M = 100001; 1094 constexpr int SQM = 320; 1095 constexpr int LGM = 20; 1096 vector<pair<int,int>> factor; 1097 int t, n[T], count_multipliers[T][M]; 1098 bitset<M> is_composite; 1099 vector<int> ans[T], a[T]; 1100 1101 inline void calculate_importants() { 1102 for(int i = 2; i < SQM; i++) 1103 if(!is_composite[i]) { 1104 for(int j = i; j < M; j *= i) 1105 factor.push_back({j,i}); 1106 for(int j = i*i; j < M; j += i) 1107 is_composite.set(j); 1108 } 1109 for(int i = SQM; i < M; i++) 1110 if(!is_composite[i]) 1111 factor.push_back({i,i}); 1112 sort(factor.begin(), factor.end()); 1113 } 1114 1115 void check(vector<int> &factors, int G) { 1116 if(factors.size() > 2u) { 1117 for(int i = 0; i < t; i++) 1118 if(ans[i].size() < factors.size()) { 1119 int count_product = (G < M? count_multipliers[i][G] : 0); 1120 bool can = true; 1121 for(auto u: factors) 1122 if(count_multipliers[i][G/factor[u].first] == count_product) { 1123 can = false; 1124 break; 1125 } 1126 if(can) 1127 ans[i] = factors; 1128 } 1129 } 1130 int bound = (factors.size() == 1 ? SQM : M); 1131 if(1LL*G/factor[factors[0]].first*factor[factors.back()].first > bound) 1132 return; 1133 for(int new_factor = factors.back(); G/factor[factors[0]].first*factor[new_factor].first <= bound; new_factor++) 1134 if(G%factor[new_factor].second) { 1135 factors.push_back(new_factor); 1136 check(factors, G*factor[new_factor].first); 1137 factors.pop_back(); 1138 } 1139 } 1140 1141 int main() { 1142 ios_base :: sync_with_stdio(false); cin.tie(nullptr); 1143 calculate_importants(); 1144 cin >> t; 1145 for(int i = 0; i < t; i++) { 1146 cin >> n[i]; 1147 a[i].resize(n[i]); 1148 for(int j = 0; j < n[i]; j++) { 1149 cin >> a[i][j]; 1150 count_multipliers[i][a[i][j]]++; 1151 } 1152 ans[i] = {a[i][0]}; 1153 sort(a[i].begin(), a[i].begin()+min(n[i], LGM)); 1154 for(int c = 0; c+1 < n[i]; c++) 1155 if(a[i][c+1]%a[i][c]) { 1156 ans[i] = {a[i][c], a[i][c+1]}; 1157 break; 1158 } 1159 for(int c = 1; c < M; c++) 1160 for(int j = c+c; j < M; j += c) 1161 count_multipliers[i][c] += count_multipliers[i][j]; 1162 } 1163 for(int i = 0; factor[i].first < SQM; i++) { 1164 vector<int> starter = {i}; 1165 check(starter, factor[i].first); 1166 } 1167 for(int i = 0; i < t; i++) { 1168 int k = ans[i].size(); 1169 cout << k << '\n'; 1170 if(k == 1u) { 1171 cout << ans[i][0] << '\n'; 1172 } else if(k == 2u) { 1173 cout << ans[i][0] << ' ' << ans[i][1] << '\n'; 1174 } else { 1175 int subset[k]; 1176 for(auto u: a[i]) { 1177 int ls = -1; 1178 for(int j = 0; j < (int)k; j++) 1179 if(u%factor[ans[i][j]].first) 1180 ls = (ls == -1? j: -2); 1181 if(ls >= 0) 1182 subset[ls] = u; 1183 } 1184 for(int j = 0; j < k; j++) 1185 cout << subset[j] << (j+1 == k? '\n' : ' '); 1186 } 1187 } 1188 return 0; 1189 } 1190 1191 /// Thank God . . . 1192 ```