2131.md (21670B)
1 Source: https://codeforces.com/blog/entry/145439 2 3 I hope you all enjoyed the contest! 4 5 **Rating Predictions** 6 7 | Predictor | A | B | C | D | E | F | G | H | 8 | --- | --- | --- | --- | --- | --- | --- | --- | --- | 9 | [AksLolCoding](/profile/AksLolCoding "Master AksLolCoding") | 800 | 900 | 1000 | 1400 | 1500 | 1800 | 1800 | — | 10 | [ALnQ417](/profile/ALnQ417 "Specialist ALnQ417") | 800 | 900 | 1100 | 1300 | 1500 | 1600 | — | — | 11 | [bookcat](/profile/bookcat "International Master bookcat") | 800 | 1200 | 1200 | 1500 | 1600 | 1600 | 1600 | 2000 | 12 | [chromate00](/profile/chromate00 "Expert chromate00") | 800 | 800 | 1000 | 1400 | 1400 | 1800 | 1800 | 2200 | 13 | [cry](/profile/cry "International Master cry") | 800 | 1000 | 1200 | 1600 | 1700 | 2100 | 2100 | 2400 | 14 | [Edeeva](/profile/Edeeva "Candidate Master Edeeva") | 800 | 800 | 1000 | 1300 | 1400 | 1600 | 1900 | — | 15 | [efishel](/profile/efishel "Master efishel") | 800 | 1000 | 1000 | 1500 | 1500 | 1800 | 1900 | 2200 | 16 | [_Equinox](/profile/_Equinox "Expert _Equinox") | 800 | 800 | 800 | 1200 | 1500 | 1600 | 1800 | — | 17 | [fatalerror](/profile/fatalerror "Candidate Master fatalerror") | 800 | 1400 | 1200 | 1600 | 1700 | 1900 | 2000 | 2100 | 18 | [-firefly-](/profile/-firefly- "Master -firefly-") | 800 | 800 | 900 | 1400 | 1400 | 1600 | 1800 | 2500 | 19 | [nifeshe](/profile/nifeshe "Grandmaster nifeshe") | 800 | 800 | 1000 | 1500 | 1600 | 1800 | 1900 | 2400 | 20 | [Non-origination](/profile/Non-origination "Expert Non-origination") | 800 | 800 | 1000 | 1600 | 1300 | 1600 | 1800 | — | 21 | [reirugan](/profile/reirugan "Candidate Master reirugan") | 800 | 900 | 1200 | 1500 | 1500 | 1800 | 1800 | — | 22 | [temporary1](/profile/temporary1 "International Master temporary1") | 800 | 800 | 900 | 1400 | 1300 | 1800 | 1900 | 2200 | 23 | [white_two](/profile/white_two "Specialist white_two") | 800 | 800 | 1200 | 1400 | 1400 | 1900 | — | — | 24 25 **Rate the contest!** 26 27 **Quality** 28 29 * Excellent contest 30 * Good contest 31 * Average contest 32 * Bad contest 33 * Horrible contest 34 35 **Difficulty** 36 37 * Trivial contest 38 * Easy contest 39 * Average contest 40 * Hard contest 41 * Impossible contest 42 43 [2131A - Lever](/contest/2131/problem/A "Codeforces Round 1042 (Div. 3)") 44 45 Idea: [-firefly-](/profile/-firefly- "Master -firefly-") 46 Preparation: [-firefly-](/profile/-firefly- "Master -firefly-") 47 Analysis: [temporary1](/profile/temporary1 "International Master temporary1") 48 49 **Hint** 50 51 The step $2$ doesn't affect step $1$. 52 53 **Solution** 54 55 Tutorial is loading... 56 57 **Code (Python)** 58 59 ``` 60 import sys 61 input = lambda: sys.stdin.readline().rstrip() 62 ii = lambda: int(input()) 63 mii = lambda: map(int, input().split()) 64 lii = lambda: list(mii()) 65 66 def solve(): 67 n = ii() 68 A = lii() 69 B = lii() 70 return sum(a - b for a, b in zip(A, B) if a > b) + 1 71 72 for _ in range(ii()): 73 print(solve()) 74 ``` 75 76 **Rate the problem!** 77 78 **Quality** 79 80 * Excellent problem 81 * Good problem 82 * Average problem 83 * Bad problem 84 * Horrible problem 85 86 **Difficulty** 87 88 * Trivial problem 89 * Easy problem 90 * Average problem 91 * Hard problem 92 * Impossible problem 93 94 [2131B - Alternating Series](/contest/2131/problem/B "Codeforces Round 1042 (Div. 3)") 95 96 Idea: [-firefly-](/profile/-firefly- "Master -firefly-") 97 Preparation: [-firefly-](/profile/-firefly- "Master -firefly-") 98 Analysis: [reirugan](/profile/reirugan "Candidate Master reirugan") 99 100 **Hint 1** 101 102 There are no much difference between the series when $n=k$ and $n=k+1$. 103 104 **Hint 2** 105 106 Construct the series from the left to the right greedily. 107 108 **Solution** 109 110 Tutorial is loading... 111 112 **Code (Python)** 113 114 ``` 115 import sys 116 input = lambda: sys.stdin.readline().rstrip() 117 ii = lambda: int(input()) 118 mii = lambda: map(int, input().split()) 119 lii = lambda: list(mii()) 120 121 def solve(): 122 n = ii() 123 if n == 1: 124 return [0] 125 ans = [-1, 3] * (n // 2) 126 if n % 2: 127 ans.append(-1) 128 else: 129 ans[-1] = 2 130 return ans 131 132 for _ in range(ii()): 133 print(*solve()) 134 ``` 135 136 **Rate the problem!** 137 138 **Quality** 139 140 * Excellent problem 141 * Good problem 142 * Average problem 143 * Bad problem 144 * Horrible problem 145 146 **Difficulty** 147 148 * Trivial problem 149 * Easy problem 150 * Average problem 151 * Hard problem 152 * Impossible problem 153 154 [2131C - Make it Equal](/contest/2131/problem/C "Codeforces Round 1042 (Div. 3)") 155 156 Idea: [Tobo](/profile/Tobo "International Master Tobo") 157 Preparation: [Tobo](/profile/Tobo "International Master Tobo"), [-firefly-](/profile/-firefly- "Master -firefly-"), [Friedrich](/profile/Friedrich "Master Friedrich") 158 Analysis: [Tobo](/profile/Tobo "International Master Tobo") 159 160 **Hint** 161 162 Consider the operations modulo $k$. 163 164 **Solution** 165 166 Tutorial is loading... 167 168 **Code (Python)** 169 170 ``` 171 import sys 172 input = lambda: sys.stdin.readline().rstrip() 173 ii = lambda: int(input()) 174 mii = lambda: map(int, input().split()) 175 lii = lambda: list(mii()) 176 177 from collections import defaultdict 178 from random import getrandbits 179 RD = getrandbits(31) 180 181 def solve(): 182 n, k = mii() 183 A = lii() 184 B = lii() 185 cnt = defaultdict(int) 186 for x in A: 187 r = x % k 188 cnt[min(r, k-r) ^ RD] += 1 189 for x in B: 190 r = x % k 191 cnt[min(r, k-r) ^ RD] -= 1 192 return all(v == 0 for v in cnt.values()) 193 194 for _ in range(ii()): 195 print('YES' if solve() else 'NO') 196 ``` 197 198 **Rate the problem!** 199 200 **Quality** 201 202 * Excellent problem 203 * Good problem 204 * Average problem 205 * Bad problem 206 * Horrible problem 207 208 **Difficulty** 209 210 * Trivial problem 211 * Easy problem 212 * Average problem 213 * Hard problem 214 * Impossible problem 215 216 [2131D - Arboris Contractio](/contest/2131/problem/D "Codeforces Round 1042 (Div. 3)") 217 218 Idea: [-firefly-](/profile/-firefly- "Master -firefly-") 219 Preparation: [-firefly-](/profile/-firefly- "Master -firefly-") 220 Analysis: [__baozii__](/profile/__baozii__ "Grandmaster __baozii__") 221 222 **Hint 1** 223 224 What is the minimum diameter achievable? 225 226 **Hint 2** 227 228 How are leaves significant? 229 230 **Solution** 231 232 Tutorial is loading... 233 234 **Code (Python)** 235 236 ``` 237 import sys 238 input = lambda: sys.stdin.readline().rstrip() 239 ii = lambda: int(input()) 240 mii = lambda: map(int, input().split()) 241 lii = lambda: list(mii()) 242 243 def solve(): 244 n = ii() 245 g = [[] for _ in range(n)] 246 deg = [0] * n 247 for _ in range(n-1): 248 u, v = mii() 249 u -= 1; v -= 1 250 g[u].append(v) 251 g[v].append(u) 252 deg[u] += 1 253 deg[v] += 1 254 if n <= 3: 255 return 0 256 257 c1 = sum(deg[u] == 1 for u in range(n)) 258 mx = max(sum(deg[v] == 1 for v in g[u]) for u in range(n)) 259 return c1 - mx 260 261 for _ in range(ii()): 262 print(solve()) 263 ``` 264 265 **Rate the problem!** 266 267 **Quality** 268 269 * Excellent problem 270 * Good problem 271 * Average problem 272 * Bad problem 273 * Horrible problem 274 275 **Difficulty** 276 277 * Trivial problem 278 * Easy problem 279 * Average problem 280 * Hard problem 281 * Impossible problem 282 283 [2131E - Adjacent XOR](/contest/2131/problem/E "Codeforces Round 1042 (Div. 3)") 284 285 Idea: [-firefly-](/profile/-firefly- "Master -firefly-") 286 Preparation: [-firefly-](/profile/-firefly- "Master -firefly-") 287 Analysis: [__baozii__](/profile/__baozii__ "Grandmaster __baozii__") 288 289 **Solution** 290 291 Tutorial is loading... 292 293 **Code (Python)** 294 295 ``` 296 import sys 297 input = lambda: sys.stdin.readline().rstrip() 298 ii = lambda: int(input()) 299 mii = lambda: map(int, input().split()) 300 lii = lambda: list(mii()) 301 302 def solve(): 303 n = ii() 304 A = lii() 305 B = lii() 306 if A[-1] != B[-1]: 307 return False 308 for i in range(n-2, -1, -1): 309 if A[i] != B[i] and A[i] ^ A[i+1] != B[i] and A[i] ^ B[i+1] != B[i]: 310 return False 311 return True 312 313 for _ in range(ii()): 314 print('YES' if solve() else 'NO') 315 ``` 316 317 **Rate the problem!** 318 319 **Quality** 320 321 * Excellent problem 322 * Good problem 323 * Average problem 324 * Bad problem 325 * Horrible problem 326 327 **Difficulty** 328 329 * Trivial problem 330 * Easy problem 331 * Average problem 332 * Hard problem 333 * Impossible problem 334 335 [2131F - Unjust Binary Life](/contest/2131/problem/F "Codeforces Round 1042 (Div. 3)") 336 337 Idea: [efishel](/profile/efishel "Master efishel"), [__baozii__](/profile/__baozii__ "Grandmaster __baozii__") 338 Preparation: [-firefly-](/profile/-firefly- "Master -firefly-") 339 Analysis: [temporary1](/profile/temporary1 "International Master temporary1"), [reirugan](/profile/reirugan "Candidate Master reirugan") 340 341 **Hint 1** 342 343 The grid possesses a significant property. Try to generate some grids with random $a$ and $b$, and understand the distribution of $0$'s and $1$'s. 344 345 **Hint 2** 346 347 For each point $(x, y)$, you can derive the answer formula like $\min(f(x,y), g(x,y))$. Note that $\displaystyle\min(f,g)=\frac{f+g}{2}-\frac{|f-g|}{2}$ 348 349 **Solution** 350 351 Tutorial is loading... 352 353 **Code (C++)** 354 355 ``` 356 #include <bits/stdc++.h> 357 using namespace std; 358 359 #define f first 360 #define s second 361 #define ll long long 362 #define pii pair<int,int> 363 #define pli pair<ll,int> 364 #define pll pair<ll,ll> 365 #define tiii tuple<int,int,int> 366 #define tiiii tuple<int,int,int,int> 367 #define pb push_back 368 #define eb emplace_back 369 #define emp emplace 370 #define mkp make_pair 371 #define mkt make_tuple 372 #define vctr vector 373 #define arr array 374 #define all(x) x.begin(), x.end() 375 #define amin(a,b) a = min(a,b) 376 #define amax(a,b) a = max(a,b) 377 #define brick(x) cout << #x << " = " << (x) << " | " 378 #define dbg(x) cout << #x << " = " << (x) << '\n' 379 #define vdbg(a) cout << #a << " = "; for(auto _x : a)cout << _x << ' '; cout << '\n' 380 #define adbg(a,n) cout << #a << " = "; for(int _i = 1; _i <= n; ++_i)cout << a[_i] << ' '; cout << '\n' 381 #define adbg0(a,n) cout << #a << " = "; for(int _i = 0; _i < n; ++_i)cout << a[_i] << ' '; cout << '\n' 382 mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count())); 383 int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); } 384 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); } 385 386 const int MOD = 1e9+7; // 998244353; 387 388 int a[200005]; 389 int b[200005]; 390 int c[200005][2]; 391 int d[200005][2]; 392 ll pf[400005][2]; 393 int cnt[400005]; 394 395 int main() { 396 ios_base::sync_with_stdio(false); 397 cin.tie(NULL); 398 int tt; 399 cin >> tt; 400 while (tt--) { 401 int n; 402 cin >> n; 403 string t; 404 cin >> t; 405 for (int i = 1; i <= n; ++i) { 406 a[i] = (t[i-1] == '1'); 407 } 408 cin >> t; 409 for (int i = 1; i <= n; ++i) { 410 b[i] = (t[i-1] == '1'); 411 } 412 const int o = n; 413 for (int i = 0; i <= 2*n; ++i) { 414 pf[i][0] = 0; 415 pf[i][1] = 0; 416 cnt[i] = 0; 417 } 418 for (int i = 1; i <= n; ++i) { 419 c[i][0] = c[i-1][0]+(a[i] == 0); 420 c[i][1] = c[i-1][1]+(a[i] == 1); 421 pf[o+c[i][0]-c[i][1]][0] += c[i][0]; 422 pf[o+c[i][0]-c[i][1]][1] += c[i][1]; 423 cnt[o+c[i][0]-c[i][1]] += 1; 424 } 425 for (int i = 1; i <= 2*n; ++i) { 426 pf[i][0] += pf[i-1][0]; 427 pf[i][1] += pf[i-1][1]; 428 cnt[i] += cnt[i-1]; 429 } 430 for (int i = 1; i <= n; ++i) { 431 d[i][0] = d[i-1][0]+(b[i] == 0); 432 d[i][1] = d[i-1][1]+(b[i] == 1); 433 } 434 ll ans = 0; 435 for (int i = 1; i <= n; ++i) { 436 int z = d[i][1]-d[i][0]; 437 // 0 worth it when delta <= z 438 ans += d[i][0]*(ll)cnt[o+z]+pf[o+z][0]; 439 ans += d[i][1]*(ll)(n-cnt[o+z])+pf[2*n][1]-pf[o+z][1]; 440 } 441 cout << ans << '\n'; 442 } 443 return 0; 444 } 445 ``` 446 447 **Rate the problem!** 448 449 **Quality** 450 451 * Excellent problem 452 * Good problem 453 * Average problem 454 * Bad problem 455 * Horrible problem 456 457 **Difficulty** 458 459 * Trivial problem 460 * Easy problem 461 * Average problem 462 * Hard problem 463 * Impossible problem 464 465 [2131G - Wafu!](/contest/2131/problem/G "Codeforces Round 1042 (Div. 3)") 466 467 Idea: [-firefly-](/profile/-firefly- "Master -firefly-") 468 Preparation: [-firefly-](/profile/-firefly- "Master -firefly-") 469 Analysis: [__baozii__](/profile/__baozii__ "Grandmaster __baozii__") 470 471 **Hint 1** 472 473 For a set $S$, how many operations are required to transform $S$ into $S \setminus {\min(S)}$? 474 475 **Hint 2** 476 477 $S$ can be represented as a binary number (though very large). 478 479 **Hint 3** 480 481 How to calculate the answer when elements in $S$ are very large? 482 483 **Solution** 484 485 Tutorial is loading... 486 487 **Code (Python)** 488 489 ``` 490 MOD = 10 ** 9 + 7 491 492 dp = [0] * 31 493 dp[0] = 1 494 for i in range(1, 31): 495 dp[i] = i + 1 496 for j in range(i): 497 dp[i] = dp[i] * dp[j] % MOD 498 499 def dfs(v, k): 500 if k == 0: 501 return 1 502 ans = v + 1 503 v = min(v - 1, 30) 504 k -= 1 505 for j in range(v + 1): 506 if k >= 1 << j: 507 ans = ans * dp[j] % MOD 508 k -= 1 << j 509 else: 510 ans = ans * dfs(j, k) % MOD 511 break 512 return ans 513 514 for _ in range(int(input())): 515 n, k = map(int, input().split()) 516 s = list(map(int, input().split())) 517 for i in range(n): 518 s[i] -= 1 519 s.sort() 520 ans = 1 521 for v in s: 522 if v <= 30 and k >= 1 << v: 523 k -= 1 << v 524 ans = ans * dp[v] % MOD 525 else: 526 ans = ans * dfs(v, k) % MOD 527 break 528 print(ans) 529 ``` 530 531 **Rate the problem!** 532 533 **Quality** 534 535 * Excellent problem 536 * Good problem 537 * Average problem 538 * Bad problem 539 * Horrible problem 540 541 **Difficulty** 542 543 * Trivial problem 544 * Easy problem 545 * Average problem 546 * Hard problem 547 * Impossible problem 548 549 [2131H - Sea, You & copriMe](/contest/2131/problem/H "Codeforces Round 1042 (Div. 3)") 550 551 Idea: [__baozii__](/profile/__baozii__ "Grandmaster __baozii__"), [-firefly-](/profile/-firefly- "Master -firefly-") 552 Preparation: [-firefly-](/profile/-firefly- "Master -firefly-") 553 Analysis: [-firefly-](/profile/-firefly- "Master -firefly-") 554 555 **Hint 1** 556 557 Let's consider an easier problem: how do we find one coprime pair from $a$? 558 559 **Step 1** 560 561 If there exists one coprime pair, it means there exists an $i$ such that 562 563 $\displaystyle\sum_{j=1}^{n}[\gcd(a_i, a_j)=1] - [a_i = 1] \gt 0$ 564 565 In other words, there are at least one other indices $j$ such that $\gcd(a_i, a_j)=1$. 566 567 Therefore, we strengthen the problem that we need to find $\displaystyle\sum_{j=1}^{n}[\gcd(a_i, a_j)=1]$ for each $i$. Here, we introduce two ways to solve the formula. 568 569 In the following discussion, we denote $f(d)$ to be the count of elements in $a$ divisible by $d$. We can precompute $f(1), f(2), \dots, f(m)$ in $O(m\log m)$ time using harmonic trick. 570 571 **Principle of Inclusion-Exclusion (PIE)** 572 573 For each $a_i$, find the set of distinct prime factors of $a_i$. Let's call this set $P_i$. For each prime factor $p_k \in P_i$, let $S_k$ be the set of elements in the array $a$ that are divisible by $p_k$. 574 575 Any number that is NOT coprime to $a_i$ must share at least one prime factor with $a_i$, so it must belongs to the set union $S_1 \cup S_2 \cup \dots \cup S_k$. By PIE we can calculate the size of the union: 576 577 $\displaystyle|S_1 \cup S_2 \cup \dots \cup S_k| = \sum_{r} |S_r| - \sum_{r \lt s} |S_r \cap S_s| + \sum_{r \lt s \lt t} |S_r \cap S_s \cap S_t| - \cdots$ 578 579 Here: 580 581 * $|S_r|$ is the count of elements in $a$ divisible by $p_r$, which is $f(p_r)$. 582 * $|S_r \cap S_s|$ is the count of elements in $a$ divisible by both $p_r$ and $p_s$, that is, divisible by $p_rp_s$, which is $f(p_rp_s)$. 583 * Similarly, $|S_r \cap S_s \cap S_t|$ is $f(p_rp_sp_t)$. 584 585 Since $f(d)$ has been precomputed, we can compute $|S_1 \cup S_2 \cup \dots \cup S_k|$ for each $i$ in $O(2^{|P_i|})$ time. Because $2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 = 9699690 \gt 10^6$, the size of $P_i$ won't exceed $7$. Therefore, the operation number is roughly $2^7 \cdot n \le 3 \cdot 10^7$, which is acceptable. 586 587 After finding the count of elements that is NOT coprime to $a_i$, we can then easily obtain $\displaystyle\sum_{j=1}^{n}[\gcd(a_i, a_j)=1]$ by subtraction. 588 589 **Mobius Inversion** 590 591 Another advanced approach to find the result is Mobius inversion. We will assume that you know the definition and property of mobius function $\mu(n)$ in the following discussion. 592 593 Since we know that $\displaystyle[\gcd(x, y) = 1] = \sum_{d|\gcd(x, y)}\mu(d)$, we can expand the orginal formula as: 594 595 $\displaystyle\sum_{j=1}^{n}[\gcd(a_i, a_j)=1] = \sum_{j=1}^{n}\sum_{d|\gcd(a_i, a_j)}\mu(d)$ 596 597 Let's swap the order of summation and get 598 599 $\displaystyle\sum_{d=1}^{m}\mu(d)\left(\sum_{j=1}^{n}[d|\gcd(a_i,a_j)]\right)$ 600 601 Because $d | \gcd(a_i, a_j)$ is equivalent to $d|a_i$ and $d|a_j$, we can simplify the formula to 602 603 $\displaystyle\sum_{d|a_i}\mu(d)\left(\sum_{j=1}^{n}[d|a_j]\right) = \sum_{d|a_i}\mu(d)f(d)$ 604 605 Thus, we can enumerate the divisors of $a_i$ for each $i$ and compute the summation above by brute force, which yields a $O(n\sqrt{m})$ or $O(nd(n))$ time. 606 607 **Hint 2** 608 609 Let's build a graph $G$ where vertex $i$ and $j$ has an undirected edge if and only if $\gcd(a_i, a_j) = 1$. The problem becomes finding a match of size $2$ in the graph. However, we only has each vertex's degrees based on the discussion above. How do we find the match only based on degrees? 610 611 **Step 2** 612 613 We use a greedy approach to obtain the match of size $2$. Let's say $G$ has at least one edge. 614 615 1. Choose a vertex $u$ with the maximum degree. 616 2. From all vertices that is connected to $u$, pick a vertex $v$ with the minimum degree. 617 3. Remove vertices $u$ and $v$ and their associated edges from $G$ to get a new graph $G^\prime$. 618 4. If there are at least one remaining edge in $G^\prime$, $G$ has a match of size $2$ that contains $(u, v)$ and the remaining edge. Otherwise, it doesn't have a match of size $2$. 619 620 **Proof of correctness** 621 622 We will prove that if $G^\prime$ contains no edges, $G$ doesn't have a match of size $2$. 623 624 Because $G^\prime$ has no edge, all of the vertices that is not isolated in $G$ connect to $u$, $v$ or both. It means $G$ has only one connected component that contains more than two vertices. To make disucssion easier, we will use $G$ to refer to $G$'s major connect component. That means all of the vertices other than $u$ and $v$ have a degree of $1$ or $2$ in $G$. 625 626 1. If all vertices other than $u$ and $v$ have a degree of $1$. If at least one vertex is connected to $u$, the minimum degree that $u$'s connected vertices becomes $1$. Since the algorithm choose $v$ with the minimum degree, $v$ also has a degree of $1$, so all vertices are connected to $u$. In this case, $G$ is a star-shaped tree, which doesn't have a match of size $2$ for obvious reason. On the other hand, if all vertices are connected to $v$, the degree of $v$ is greater than $u$, which is impossible become the degree of $u$ is maximum. 627 2. If exactly one vertex other than $u$ and $v$ has a degree of $2$, it must connect to both $u$ and $v$. Similar to the discussion above, we can prove that no other vertex can be connected to either $u$ or $v$. In this case, $G$ is a three-vertex loop, or $K_3$, which doesn't have a match of size $2$. 628 3. If more than two vertices other than $u$ and $v$ have a degree of $2$, it means $v$ has a degree of more than $3$. Let's denote a vertex that connects to both $u$ and $v$ as $w$, then $\mathrm{deg}(w) = 2 \lt 3 \le \mathrm{deg}(v)$. Because $w$ is also connected to $u$, it contradicts to the step $2$ of the algorithm. 629 630 For our problem, for each $i$, the degree is $\displaystyle\sum_{j=1}^{n}[\gcd(a_i, a_j)=1] - [a_i = 1]$. We can then brute force to find the first edge, remove it, and then try to find the second edge. 631 632 **Code (C++)** 633 634 ``` 635 #include <bits/stdc++.h> 636 using i64 = long long; 637 constexpr int V = 1e6 + 10; 638 639 std::array<int, V> mu, comp; 640 std::vector<int> primes; 641 642 void solve() { 643 int n, m = 0; 644 std::cin >> n; 645 std::vector<int> a(n); 646 for (int i = 0; i < n; ++i) { 647 std::cin >> a[i]; 648 m = std::max(m, a[i]); 649 } 650 std::vector<int> mul(m+1), deg(n), mp(m+1); 651 for (int i = 0; i < n; ++i) { 652 mp[a[i]]++; 653 } 654 for (int j = 1; j <= m; ++j) { 655 for (int x = j; x <= m; x += j) { 656 mul[j] += mp[x]; 657 } 658 } 659 for (int i = 0; i < n; ++i) { 660 for (int j = 1; j * j <= a[i]; ++j) { 661 if (a[i] % j == 0) { 662 deg[i] += mu[j] * mul[j]; 663 if (j * j < a[i]) { 664 deg[i] += mu[a[i] / j] * mul[a[i] / j]; 665 } 666 } 667 } 668 if (a[i] == 1) --deg[i]; 669 } 670 std::array<int, 4> ans; 671 int u = 0, v = 0, mind = INT32_MAX; 672 for (int i = 1; i < n; ++i) { 673 if (deg[i] > deg[u]) { 674 u = i; 675 } 676 } 677 if (!deg[u]) { 678 std::cout << "0\n"; 679 return; 680 } 681 deg[u] = 0; 682 for (int i = 0; i < n; ++i) { 683 if (i == u) continue; 684 if (std::gcd(a[i], a[u]) == 1) { 685 --deg[i]; 686 if (mind > deg[i]) { 687 mind = deg[i]; 688 v = i; 689 } 690 } 691 } 692 ans[0] = u; 693 ans[1] = v; 694 deg[v] = 0; 695 for (int i = 0; i < n; ++i) { 696 if (i == u || i == v) continue; 697 if (std::gcd(a[i], a[v]) == 1) { 698 --deg[i]; 699 } 700 } 701 u = 0; 702 for (int i = 1; i < n; ++i) { 703 if (deg[i] > deg[u]) { 704 u = i; 705 } 706 } 707 if (!deg[u]) { 708 std::cout << "0\n"; 709 return; 710 } 711 v = -1; 712 for (int i = 0; i < n; ++i) { 713 if (i == u || !deg[i]) continue; 714 if (std::gcd(a[i], a[u]) == 1) { 715 v = i; 716 break; 717 } 718 } 719 assert(v >= 0); 720 ans[2] = u; ans[3] = v; 721 for (int i = 0; i < 4; ++i) { 722 std::cout << ans[i] + 1 << " \n"[i == 3]; 723 } 724 } 725 726 int main() { 727 std::cin.tie(nullptr)->sync_with_stdio(false); 728 int T = 1; 729 std::cin >> T; 730 mu[1] = 1; 731 for (int i = 2; i < V; ++i) { 732 if (!comp[i]) { 733 primes.emplace_back(i); 734 mu[i] = -1; 735 } 736 for (auto p: primes) { 737 int q = i * p; 738 if (q >= V) break; 739 comp[q] = true; 740 if (i % p == 0) { 741 mu[q] = 0; 742 break; 743 } else { 744 mu[q] = -mu[i]; 745 } 746 } 747 } 748 while (T--) solve(); 749 return 0; 750 } 751 ``` 752 753 **Rate the problem!** 754 755 **Quality** 756 757 * Excellent problem 758 * Good problem 759 * Average problem 760 * Bad problem 761 * Horrible problem 762 763 **Difficulty** 764 765 * Trivial problem 766 * Easy problem 767 * Average problem 768 * Hard problem 769 * Impossible problem