1191.md (42428B)
1 Source: https://codeforces.com/blog/entry/68314 2 3 [1191A - Tokitsukaze и улучшение](/contest/1191/problem/A "Codeforces Round 573 (Div. 2)") 4 5 Idea: [tokitsukaze](/profile/tokitsukaze "Мастер tokitsukaze") 6 7 **Tutorial** 8 9 Just enumerating the increment can pass. 10 11 However, by increasing at most $2$ points, the value of her HP can always become an odd number, and thus the highest possible level is either $A$ or $B$. We can just solve case by case. 12 13 **Solution (by Claris)** 14 15 ``` 16 #include<cstdio> 17 int x,i,A;char B; 18 char cal(int x){ 19 x%=4; 20 if(x==0)return 'D'; 21 if(x==1)return 'A'; 22 if(x==2)return 'C'; 23 return 'B'; 24 } 25 int main(){ 26 scanf("%d",&x); 27 A=0; 28 B=cal(x); 29 for(i=1;i<=2;i++){ 30 if(cal(x+i)<B){ 31 A=i; 32 B=cal(x+i); 33 } 34 } 35 printf("%d %c",A,B); 36 } 37 ``` 38 39 **Solution (by tokitsukaze)** 40 41 ``` 42 #include <bits/stdc++.h> 43 using namespace std; 44 int main() 45 { 46 int x; 47 cin>>x; 48 if(x%4==0) puts("1 A"); 49 else if(x%4==1) puts("0 A"); 50 else if(x%4==2) puts("1 B"); 51 else if(x%4==3) puts("2 A"); 52 return 0; 53 } 54 ``` 55 56 [1191B - Tokitsukaze и маджонг](/contest/1191/problem/B "Codeforces Round 573 (Div. 2)") 57 58 Idea: [tokitsukaze](/profile/tokitsukaze "Мастер tokitsukaze"), [2014CAIS01](/profile/2014CAIS01 "Мастер 2014CAIS01") 59 60 **Tutorial** 61 62 There are only two types of **mentsu**s, so you can enumerate the **mentsu** you want her to form, and check the difference between that and those currently in her hand. 63 64 Alternatively, you can find out that the answer is at most $2$, since she can draw two extra identical tiles which are the same as one of those in her hand. You may enumerate at most $1$ extra tile for her and check if it can contribute to a **mentsu**. If she can't, the answer will be $2$. 65 66 **Solution (by skywalkert)** 67 68 ``` 69 #include <bits/stdc++.h> 70 using namespace std; 71 int main() { 72 int idx[257] = {}, c[3][9] = {}, ans = 2; 73 idx['m'] = 1; 74 idx['p'] = 2; 75 idx['s'] = 3; 76 for(int i = 0; i < 3; ++i) { 77 char buf[3]; 78 scanf("%s", buf); 79 ++c[idx[buf[1]] - 1][buf[0] - '1']; 80 } 81 for(int i = 0; i < 3; ++i) 82 for(int j = 0; j < 9; ++j) { 83 ans = min(ans, 3 - c[i][j]); 84 if(j + 2 < 9) 85 ans = min(ans, 3 - !!c[i][j] - !!c[i][j + 1] - !!c[i][j + 2]); 86 } 87 printf("%d\n", ans); 88 return 0; 89 } 90 ``` 91 92 **Solution (by isaf27)** 93 94 ``` 95 //#pragma GCC optimize("O3") 96 #include <bits/stdc++.h> 97 98 using namespace std; 99 100 //defines 101 typedef long long ll; 102 typedef long double ld; 103 #define TIME clock() * 1.0 / CLOCKS_PER_SEC 104 #define prev _prev 105 #define y0 y00 106 107 //permanent constants 108 const ld pi = acos(-1.0); 109 const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; 110 const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; 111 const int dx[4] = {0, 1, 0, -1}; 112 const int dy[4] = {1, 0, -1, 0}; 113 const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0}; 114 const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1}; 115 const int alf = 26; 116 const int dig = 10; 117 const int two = 2; 118 const int th = 3; 119 const ll prost = 239; 120 const ll bt = 30; 121 const ld eps = 1e-7; 122 const ll INF = (ll)(1e18 + 239); 123 const int BIG = (int)(1e9 + 239); 124 const int MOD = 998244353; 125 const ll MOD2 = (ll)MOD * (ll)MOD; 126 127 //random 128 mt19937 rnd(239); //(chrono::high_resolution_clock::now().time_since_epoch().count()); 129 130 //constants 131 const int M = (int)(2e5 + 239); 132 const int N = (int)(2e3 + 239); 133 const int L = 20; 134 const int T = (1 << 20); 135 const int B = (int)sqrt(M); 136 const int X = 1e4 + 239; 137 138 bool check(string a, string b, string c) 139 { 140 if (a == b && b == c) return true; 141 if (a > b) swap(a, b); 142 if (b > c) swap(b, c); 143 if (a > b) swap(a, b); 144 if (a[1] == b[1] && b[1] == c[1]) 145 { 146 if (a[0] + 1 == b[0] && b[0] + 1 == c[0]) 147 return true; 148 } 149 return false; 150 } 151 152 int32_t main() 153 { 154 #ifdef ONPC 155 freopen("input.txt", "r", stdin); 156 #endif 157 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 158 string a, b, c; 159 cin >> a >> b >> c; 160 if (check(a, b, c)) 161 { 162 cout << "0"; 163 return 0; 164 } 165 vector<string> var; 166 for (int i = 1; i <= 9; i++) 167 { 168 string s = ""; 169 s += (char)(i + '0'); 170 var.push_back(s + "m"); 171 var.push_back(s + "p"); 172 var.push_back(s + "s"); 173 } 174 for (string s : var) 175 { 176 if (check(s, a, b)) 177 { 178 cout << "1"; 179 return 0; 180 } 181 if (check(s, a, c)) 182 { 183 cout << "1"; 184 return 0; 185 } 186 if (check(s, b, c)) 187 { 188 cout << "1"; 189 return 0; 190 } 191 } 192 cout << "2"; 193 return 0; 194 } 195 ``` 196 197 [1190A - Tokitsukaze и выбрасывание вещей](/contest/1190/problem/A "Codeforces Round 573 (Div. 1)") / [1191C - Tokitsukaze и выбрасывание вещей](/contest/1191/problem/C "Codeforces Round 573 (Div. 2)") 198 199 Idea: [tokitsukaze](/profile/tokitsukaze "Мастер tokitsukaze") 200 201 **Tutorial** 202 203 The order of discarding is given, so we can simulate the process of discarding. 204 205 In each time, we can calculate the page that contains the first special item that has not been discarded, and then locate all the special items that need to be discarded at one time. Repeat this process until all special items are discarded. 206 207 Each time at least one item would be discarded, so the time complexity is $\mathcal{O}(m)$. 208 209 **Solution (by tokitsukaze)** 210 211 ``` 212 #include <bits/stdc++.h> 213 using namespace std; 214 typedef long long ll; 215 const int MAX=1e5+10; 216 ll p[MAX]; 217 int main() 218 { 219 ll n,m,k; 220 scanf("%lld%lld%lld",&n,&m,&k); 221 for(int i=1;i<=m;i++) scanf("%lld",&p[i]); 222 int ans=0; 223 int sum=0; 224 int now=1; 225 while(now<=m) 226 { 227 ll r=((p[now]-sum-1)/k+1)*k+sum; 228 // cout<<"r:"<<r<<endl; 229 while(now<=m&&p[now]<=r) 230 { 231 sum++; 232 now++; 233 } 234 ans++; 235 } 236 printf("%d\n",ans); 237 return 0; 238 } 239 ``` 240 241 [1190B - Tokitsukaze, CSL и игра с камнями](/contest/1190/problem/B "Codeforces Round 573 (Div. 1)") / [1191D - Tokitsukaze, CSL и игра с камнями](/contest/1191/problem/D "Codeforces Round 573 (Div. 2)") 242 243 Idea: [tokitsukaze](/profile/tokitsukaze "Мастер tokitsukaze") 244 245 **Tutorial** 246 247 Unless the first player must lose after the first move, the numbers of stones in these piles should form a permutation obtained from $0$ to $(n - 1)$ in the end, in order to ensure that there are no two piles include the same number of stones. 248 249 Let's use $cnt[x]$ to represent the number of piles which have exactly $x$ stones in the beginning. There are four cases that Tokitsukaze will lose after the first move: 250 251 * $cnt[0] \gt 1$; 252 * $cnt[x] \gt 2$ for some $x$; 253 * $cnt[x] \gt 1$ and $cnt[y] \gt 1$ for some $x$, $y$ ($x \neq y$); 254 * $cnt[x] \gt 1$ and $cnt[x - 1] \gt 0$ for some $x$. 255 256 If Tokitsukaze won't lose after the first move, then we only need to check the parity of the total number of stones that can be taken. 257 258 By the way, if you don't want to discuss the above four cases, you can just enumerate her first move. 259 260 **Solution (by tokitsukaze)** 261 262 ``` 263 #include <bits/stdc++.h> 264 using namespace std; 265 typedef long long ll; 266 const int MAX=1e5+10; 267 int a[MAX]; 268 int main() 269 { 270 int n; 271 cin>>n; 272 map<int,int> mp; 273 int ok=1; 274 for(int i=1;i<=n;i++) 275 { 276 cin>>a[i]; 277 mp[a[i]]++; 278 ok&=(mp[a[i]]<3); //situation 1: one >=3 279 } 280 int cnt=0; 281 for(auto it:mp) 282 { 283 if(it.second>=2) cnt++; 284 } 285 ok&=(cnt<=1);// situation 2: more than two >=2 286 for(auto it:mp) 287 { 288 if(it.second==2) 289 { 290 ok&=(mp.count(it.first-1)==0);// situation 3: reduce one but add another 291 if(it.first==0) ok=0;// situation 4: two pile is zero 292 } 293 } 294 if(!ok) return 0*puts("cslnb"); 295 // normal situation 296 sort(a+1,a+1+n); 297 ll s=0; 298 for(int i=1;i<=n;i++) 299 { 300 assert(a[i]>=i-1); 301 s+=a[i]-(i-1); 302 } 303 s%=2; 304 return 0*puts(s?"sjfnb":"cslnb"); 305 } 306 ``` 307 308 **Solution (by skywalkert)** 309 310 ``` 311 #include <bits/stdc++.h> 312 using namespace std; 313 const int maxn = (int)1e5 + 1; 314 int n, a[maxn], c[3]; 315 void update(int x, int d) { 316 static map<int, int> ctr; 317 int &v = ctr[x]; 318 --c[min(v, 2)]; 319 v += d; 320 ++c[min(v, 2)]; 321 } 322 int main() { 323 scanf("%d", &n); 324 for(int i = 0; i < n; ++i) { 325 scanf("%d", a + i); 326 update(a[i], 1); 327 } 328 bool chk = 0; 329 for(int i = 0; !chk && i < n; ++i) 330 if(a[i]) { 331 update(a[i], -1); 332 update(a[i] - 1, 1); 333 chk |= !c[2]; 334 update(a[i] - 1, -1); 335 update(a[i], 1); 336 } 337 if(chk) { 338 chk = 0; 339 for(int i = 0; i < n; ++i) 340 chk ^= (a[i] + i) & 1; 341 } 342 puts(chk ? "sjfnb" : "cslnb"); 343 return 0; 344 } 345 ``` 346 347 [1190C - Tokitsukaze и дуэль](/contest/1190/problem/C "Codeforces Round 573 (Div. 1)") / [1191E - Tokitsukaze и дуэль](/contest/1191/problem/E "Codeforces Round 573 (Div. 2)") 348 349 Idea: [teitoku](/profile/teitoku "Кандидат в мастера teitoku"), [winterzz1](/profile/winterzz1 "Кандидат в мастера winterzz1") 350 351 **Tutorial** 352 353 If a player can make a move from a situation to that situation again, this player will not lose. Except for some initial situations, one can move from almost every situation to itself. Based on these two conclusions, we can get a solution. 354 355 If Tokitsukaze cannot win after her first move, she cannot win in the future. In this case, we can quickly check if $k$ is so limited that she cannot win. 356 357 After her first move, it is possible that Quailty wins in the next move. If he cannot, in order to prevent failure, he can just leave the situation to his opponent by doing useless flipping and thus result in a draw. 358 359 Therefore, we can check if no matter how Tokitsukaze moves, Quailty has no chance to win after his first move. It can be easily checked linearly if we do some precalculation and enumerate Tokitsukaze's first move. Alternatively, we can find and check the pattern of initial situations in which Quailty can win. 360 361 **Solution (by quailty)** 362 363 ``` 364 #include<bits/stdc++.h> 365 using namespace std; 366 const int MAXN=100005; 367 int n,k; 368 char str[MAXN]; 369 vector<int> loc[2]; 370 int main() 371 { 372 scanf("%d%d%s",&n,&k,str); 373 for(int i=0;i<n;i++) 374 loc[str[i]-'0'].push_back(i); 375 if(loc[0].empty() || loc[1].empty()) 376 return 0*printf("tokitsukaze\n"); 377 int flag=0; 378 for(int l=0,r=k-1;r<n;l++,r++) 379 { 380 vector<int> tmp[2]; 381 for(int i=0;i<2;i++) 382 { 383 if(loc[i].front()<l || loc[i].front()>r) 384 tmp[i].push_back(loc[i].front()); 385 if(loc[i].back()<l || loc[i].back()>r) 386 tmp[i].push_back(loc[i].back()); 387 auto itr=lower_bound(loc[i].begin(),loc[i].end(),l); 388 if(itr!=loc[i].begin()) 389 tmp[i].push_back(*--itr); 390 itr=upper_bound(loc[i].begin(),loc[i].end(),r); 391 if(itr!=loc[i].end()) 392 tmp[i].push_back(*itr); 393 sort(tmp[i].begin(),tmp[i].end()); 394 } 395 if(tmp[0].empty() || tmp[1].empty()) 396 return 0*printf("tokitsukaze\n"); 397 flag|=(tmp[0].back()-tmp[0].front()>=k 398 || tmp[1].back()-tmp[1].front()>=k); 399 } 400 return 0*printf("%s\n",(flag ? "once again" : "quailty")); 401 } 402 ``` 403 404 **Solution (by skywalkert)** 405 406 ``` 407 #include <bits/stdc++.h> 408 using namespace std; 409 const int maxn = (int)1e5 + 1; 410 int n, m, p[maxn], lft[maxn], rht[maxn]; 411 char buf[maxn]; 412 int main() { 413 scanf("%d%d%s", &n, &m, buf); 414 for(int i = 0, las[2] = {-1, -1}; i < n; ++i) { 415 int o = buf[i] - '0'; 416 lft[i] = las[o ^ 1]; 417 las[o] = i; 418 } 419 for(int i = n - 1, las[2] = {n, n}; i >= 0; --i) { 420 int o = buf[i] - '0'; 421 rht[i] = las[o ^ 1]; 422 las[o] = i; 423 } 424 bool fir = 0, sec = 1; 425 for(char op = '0'; op <= '1' && !fir; ++op) { 426 int sz = 0; 427 for(int i = 0; i < n; ++i) 428 if(buf[i] != op) 429 p[sz++] = i; 430 for(int L = 0, R = m - 1, pL = 0, pR = -1; R < n; ++L, ++R) { 431 for( ; pL < sz && p[pL] < L; ++pL); 432 for( ; pR + 1 < sz && p[pR + 1] <= R; ++pR); 433 if(pL == 0 && pR == sz - 1) { 434 fir = 1; 435 break; 436 } 437 int uL = p[pL ? 0 : pR + 1]; 438 int uR = p[pR < sz - 1 ? sz - 1 : pL - 1]; 439 int vL = uL > 0 ? 0 : min(rht[uL], uR + 1); 440 int vR = uR < n - 1 ? n - 1 : max(lft[uR], uL - 1); 441 sec &= uR - uL + 1 <= m || vR - vL + 1 <= m; 442 } 443 } 444 puts(fir ? "tokitsukaze" : (sec ? "quailty" : "once again")); 445 return 0; 446 } 447 ``` 448 449 **Solution (by winterzz1)** 450 451 ``` 452 #include<bits/stdc++.h> 453 using namespace std; 454 const int MAXN=1000005; 455 int n,k,T; 456 int a[MAXN],sum[MAXN]; 457 int q_sum(int l,int r) 458 { 459 if(l>r)return 0; 460 return sum[r]-sum[l-1]; 461 } 462 bool check_fir() 463 { 464 for(int i=1;i+k-1<=n;++i) 465 { 466 int lala=q_sum(1,i-1)+q_sum(i+k,n); 467 if(lala==0||lala+k==n)return true; 468 } 469 return false; 470 } 471 bool check_sec() 472 { 473 if(k*2<n||k==1)return false; 474 int len=n-k-1; 475 for(int i=2;i<=len;++i) 476 { 477 if(a[i]!=a[i-1]||a[n-i+1]!=a[n-i+2])return false; 478 } 479 if(a[len]==a[len+1]||a[n-len]==a[n-len+1]||a[1]==a[n])return false; 480 return true; 481 } 482 int main() 483 { 484 scanf("%d %d",&n,&k); 485 for(int i=1;i<=n;++i) 486 { 487 scanf("%1d",&a[i]); 488 sum[i]=sum[i-1]+a[i]; 489 } 490 if(check_fir()) 491 { 492 printf("tokitsukaze\n"); 493 } 494 else 495 { 496 if(check_sec()) 497 { 498 printf("quailty\n"); 499 } 500 else 501 { 502 printf("once again\n"); 503 } 504 } 505 return 0; 506 } 507 ``` 508 509 [1190D - Tokitsukaze и странный прямоугольник](/contest/1190/problem/D "Codeforces Round 573 (Div. 1)") / [1191F - Tokitsukaze и странный прямоугольник](/contest/1191/problem/F "Codeforces Round 573 (Div. 2)") 510 511 Idea: [tokitsukaze](/profile/tokitsukaze "Мастер tokitsukaze") 512 513 **Tutorial** 514 515 For each strange rectangular area and its corresponding set of points, we only need to focus on the lowest $y$-coordinate $yB$, the leftmost $x$-coordinate $xL$ and the rightmost $x$-coordinate $xR$ of points in this set. Different sets must have different $yB$, $xL$, $xR$, so we can count them by enumerating these values. 516 517 Let's enumerate $yB$ first. Then, we need to list all the possible $x$-coordinates of points $(x_i, y_i)$ satisfying that $y_i \geq yB$ and mark every possible $x'$ satisfying there is a point $(x', yB)$. By doing so, we can make sure when enumerating $xL$ and $xR$, the requirement for $yB$ is met as well. However, enumerating forcibly, which is in time complexity $\mathcal{O}(n^3)$, is too slow to pass, so let's optimize the enumeration step by step. 518 519 Let's pick and sort the points $(x'_1, yB), (x'_2, yB), \ldots, (x'_m, yB)$ from left to right. Assuming that $x'_0 = 0$, and $(x'_j, yB)$ is the leftmost point of them that is in the chosen set, we can count the number of aforementioned different $x$-coordinates in ranges $[x'_{j - 1} + 1, x'_j]$ and $[x'_j, \infty)$ and then count the number of possible pairs $(xL, xR)$ immediately. More specifically, let $cnt(l, r)$ be the number of different $x$-coordinates of points in the area $\lbrace (x, y) | l \leq x \leq r, y \geq yB \rbrace$, and we know the number of possible pairs $(xL, xR)$ is $cnt(x'_{j - 1} + 1, x'_j) \cdot cnt(x'_j, \infty)$. After precalculating $c(1, x)$ for each $yB$, we can reduce the time complexity into $\mathcal{O}(n^2)$. 520 521 The very last step is using the trick of sweeping lines. We can enumerate $yB$ from highest to lowest, and during that process, use data structures to maintain possible $x$-coordinates. What we need to implement is to maintain a container, check if a coordinate is already in the container, add a coordinate to the container, and query the number of coordinates in a range. These requirements can be easily achieved by Fenwick tree, segment tree or others. With the last optimization, we can solve in time complexity $\mathcal{O}(n \log n)$. 522 523 By the way, there also exist solutions using other approaches, such as *divide and conquer*. 524 525 **Solution (by tokitsukaze)** 526 527 ``` 528 #include <bits/stdc++.h> 529 using namespace std; 530 #define mem(a,b) memset((a),(b),sizeof(a)) 531 #define MP make_pair 532 #define pb push_back 533 #define fi first 534 #define se second 535 #define sz(x) (int)x.size() 536 #define all(x) x.begin(),x.end() 537 #define sqr(x) (x)*(x) 538 using namespace __gnu_cxx; 539 typedef long long ll; 540 typedef unsigned long long ull; 541 typedef pair<int,int> PII; 542 typedef pair<ll,ll> PLL; 543 typedef pair<int,ll> PIL; 544 typedef pair<ll,int> PLI; 545 typedef vector<int> VI; 546 typedef vector<ll> VL; 547 void go(); 548 int main(){ 549 #ifdef tokitsukaze 550 // freopen("TEST.txt","r",stdin); 551 #endif 552 go();return 0; 553 } 554 const int INF=0x3f3f3f3f; 555 const ll LLINF=0x3f3f3f3f3f3f3f3fLL; 556 const double PI=acos(-1.0); 557 const double eps=1e-6; 558 const int MAX=2e5+10; 559 const ll mod=998244353; 560 /********************************* head *********************************/ 561 struct Fenwick_Tree 562 { 563 int bit[MAX]; 564 int n; 565 void init(int _n){n=_n;mem(bit,0);} 566 int lowbit(int x){return x&(-x);} 567 void insert(int x,int v) 568 { 569 while(x<=n) 570 { 571 bit[x]+=v; 572 x+=lowbit(x); 573 } 574 } 575 int get(int x) 576 { 577 int res=0; 578 while(x) 579 { 580 res+=bit[x]; 581 x-=lowbit(x); 582 } 583 return res; 584 } 585 int query(int l,int r) 586 { 587 return get(r)-get(l-1); 588 } 589 }tr; 590 VI x[MAX],y; 591 void go() 592 { 593 int n,i,tot,pre; 594 ll ans; 595 while(~scanf("%d",&n)) 596 { 597 tr.init(n); 598 y.clear(); 599 map<int,int> idx,idy,cntx; 600 tot=0; 601 for(i=0;i<n;i++) 602 { 603 int X,Y; 604 scanf("%d%d",&X,&Y); 605 if(!idy.count(Y)) 606 { 607 x[tot].clear(); 608 idy[Y]=tot++; 609 y.pb(Y); 610 } 611 x[idy[Y]].pb(X); 612 cntx[X]++; 613 } 614 tot=0; 615 for(auto it:cntx) 616 { 617 idx[it.fi]=++tot; 618 tr.insert(tot,1); 619 } 620 sort(all(y)); 621 ans=0; 622 for(auto Y:y) 623 { 624 sort(all(x[idy[Y]])); 625 pre=1; 626 for(auto X:x[idy[Y]]) 627 { 628 ans+=1LL*tr.query(pre,idx[X])*tr.query(idx[X],tot); 629 pre=idx[X]+1; 630 cntx[X]--; 631 if(cntx[X]==0) 632 { 633 cntx.erase(X); 634 tr.insert(idx[X],-1); 635 } 636 } 637 } 638 printf("%lld\n",ans); 639 } 640 } 641 ``` 642 643 **Solution (by winterzz1)** 644 645 ``` 646 #include <bits/stdc++.h> 647 using namespace std; 648 //priority_queue<int> q; 649 //priority_queue<int,vector<int>, greater<int> > q; 650 #include <ext/pb_ds/tree_policy.hpp> 651 #include <ext/pb_ds/assoc_container.hpp> 652 using namespace __gnu_pbds; 653 654 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> less_rbtree; 655 typedef tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update> greater_rbtree; 656 657 typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> multi_less_rbtree; 658 typedef tree<pair<int,int>, null_type, greater<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> multi_greater_rbtree; 659 const int MAXN=300005; 660 less_rbtree div_tree; 661 long long ans; 662 struct node 663 { 664 int x,y; 665 }p[MAXN],temp[MAXN]; 666 int n; 667 bool cmp1(const node & A,const node & B) 668 { 669 return A.x<B.x; 670 } 671 bool cmp2(const node & A,const node & B) 672 { 673 if(A.y!=B.y)return A.y>B.y; 674 return A.x<B.x; 675 } 676 void div_algorithm(int l,int r) 677 { 678 if(l>r)return; 679 div_tree.clear(); 680 for(int i=l;i<=r;++i) 681 { 682 temp[i]=p[i]; 683 } 684 int mid_line=p[(l+r)>>1].x; 685 long long preans=ans; 686 int lpos=-1,rpos=-1; 687 sort(temp+l,temp+r+1,cmp2); 688 for(int i=l;i<=r;++i) 689 { 690 div_tree.insert(temp[i].x); 691 if(temp[i].x<=mid_line) 692 { 693 if(lpos==-1||lpos<temp[i].x) 694 { 695 lpos=temp[i].x; 696 } 697 } 698 if(temp[i].x>=mid_line) 699 { 700 if(rpos==-1||rpos>temp[i].x) 701 { 702 rpos=temp[i].x; 703 } 704 } 705 if(i==r||temp[i+1].y!=temp[i].y) 706 { 707 708 long long lsum=div_tree.order_of_key(lpos+1); 709 long long Lsum=div_tree.order_of_key(mid_line+1); 710 long long rsum=div_tree.size()-div_tree.order_of_key(rpos); 711 long long Rsum=div_tree.size()-div_tree.order_of_key(mid_line); 712 if(lpos==-1) 713 { 714 ans+=Lsum*rsum; 715 } 716 else if(rpos==-1) 717 { 718 ans+=lsum*Rsum; 719 } 720 else 721 { 722 ans+=lsum*Rsum+Lsum*rsum-lsum*rsum; 723 } 724 lpos=-1; 725 rpos=-1; 726 } 727 } 728 int pin1=l,pin2=r; 729 while(p[pin1].x!=mid_line)++pin1; 730 while(p[pin2].x!=mid_line)--pin2; 731 div_algorithm(l,pin1-1); 732 div_algorithm(pin2+1,r); 733 } 734 int main() 735 { 736 scanf("%d",&n); 737 for(int i=1;i<=n;++i) 738 { 739 scanf("%d %d",&p[i].x,&p[i].y); 740 } 741 sort(p+1,p+1+n,cmp1); 742 div_algorithm(1,n); 743 printf("%I64d\n",ans); 744 return 0; 745 } 746 ``` 747 748 [1190E - Tokitsukaze и взрыв](/contest/1190/problem/E "Codeforces Round 573 (Div. 1)") 749 750 Idea: [chenjb](/profile/chenjb "Гроссмейстер chenjb"), [Subconscious](/profile/Subconscious "Международный гроссмейстер Subconscious") 751 752 **Tutorial** 753 754 It is obvious that we can binary search the answer because we can pull any line closer to $O$ and the situation won't change. Applying a binary search, we focus on if it is possible to set $m$ barriers with the same distance to $O$ and meet the requirement. By doing so, we can draw a circle whose center is $O$ such that the closest point to $O$ on each barrier is on the circumference. Then it becomes a classic problem — for each barrier we can get the angle range of its closest point on the circle, and we have to choose at most $m$ points on the circle to ensure that there is at least one point within each range. 755 756 This kind of greedy trick is very simple on a sequence. As to ranges on a sequence, you only have to sort all ranges in increasing order of left endpoint and take every necessary right endpoint. As to ranges on a circle, you can enumerate a position to break the circle into a sequence. But if you enumerate as the same way on the sequence, the time complexity will be $\mathcal{O}(n^2)$ which is not enough. 757 758 Instead, we can double and extend these ranges into $2 n$ ranges and then regard them as on a sequence. We can do some precalculation, such as if we want to choose a point to cover the $i$-th sorted range and other ranges in its right as many as possible, what is the next range that we cannot cover. Let's denote that as $f[i][0]$, and then we can calculate the next range after $2^p$ repeated steps from the $i$-th range as $f[i][p]$, which can be obtained from $f[f[i][p - 1]][p - 1]$. After preparation, we can enumerate the beginning position and use binary lifting method, each time in complexity $\mathcal{O}(\log m)$, to know that whether we can use $m$ steps to cover all the ranges. 759 760 Therefore, the total time complexity can be $\mathcal{O}(n \log m \log D)$, where $D$ is the precision requirement. 761 762 **Solution (by chenjb)** 763 764 ``` 765 #include <cstdio> 766 #include <cstdlib> 767 #include <cstring> 768 #include <cmath> 769 #include <algorithm> 770 #define pi acos(-1.0) 771 #define LOG 20 772 #define eps 1e-9 773 774 using namespace std; 775 const int N = 500010; 776 const double twopi = 2*acos(-1.0); 777 int n,m,tot,fa[N*2][LOG]; 778 bool nd[N*2]; 779 double xx[N],yy[N],di[N]; 780 struct Segment 781 { 782 double l,r; bool typ; 783 Segment(){} 784 Segment(double l,double r,bool typ):l(l),r(r),typ(typ){} 785 }q[N*2]; 786 bool cmp(const Segment &a,const Segment &b){ if(a.typ!=b.typ) return a.typ<b.typ; return a.l<b.l; } 787 bool check(double cur) 788 { 789 tot = 0; 790 for(int i=1;i<=n;i++) 791 { 792 double deg = atan2(yy[i],xx[i]), p = acos(cur/di[i]); 793 q[++tot] = Segment(deg-p,deg+p,0); 794 q[++tot] = Segment(deg-p+twopi,deg+p+twopi,1); 795 } 796 sort(q+1,q+1+tot,cmp); 797 double mr = 2147483600; 798 memset(nd,1,tot+1); 799 for(int i=tot;i;i--) 800 { 801 if(q[i].r>=mr) nd[i] = 0; 802 else mr = q[i].r; 803 } 804 tot = 0; 805 for(int i=1;i<=n;i++) if(nd[i]) q[++tot] = q[i]; 806 for(int i=1;i<=tot;i++) q[i+tot] = Segment(q[i].l+twopi,q[i].r+twopi,1); 807 tot <<= 1; 808 int j = 1; 809 for(int i=1;i<=tot;i++) 810 { 811 while(j<=tot&&q[i].r>=q[j].l) j++; 812 fa[i][0] = j; 813 } 814 for(int j=1;(1<<j)<=tot;j++) 815 for(int i=1;i<=tot;i++) 816 fa[i][j] = fa[fa[i][j-1]][j-1]; 817 for(int i=1;(i<<1)<=tot;i++) 818 { 819 int p = i, tmp = 0; 820 for(int k=m;k;k>>=1,tmp++) 821 if(k&1) p = fa[p][tmp]; 822 if(p==0||p>=i+(tot>>1)) return true; 823 } 824 return false; 825 } 826 int main() 827 { 828 scanf("%d%d",&n,&m); 829 double l = 0, r = 1e100; 830 for (int i=1;i<=n;i++) { 831 scanf("%lf%lf",&xx[i],&yy[i]); 832 di[i] = sqrt(xx[i]*xx[i]+yy[i]*yy[i]); 833 r = min(r, di[i]); 834 } 835 if(m>=n) { 836 printf("%.10f\n",r); 837 return 0; 838 } 839 while (r - l > eps) { 840 double mid = (l + r) / 2; 841 if (check(mid)) l = mid; else r = mid; 842 } 843 printf("%.10f\n", l); 844 return 0; 845 } 846 ``` 847 848 **Solution (by quailty)** 849 850 ``` 851 #include<bits/stdc++.h> 852 using namespace std; 853 854 typedef long long ll; 855 typedef long double db; 856 857 const int MAXN=100005; 858 const int DEP=18; 859 860 vector<pair<int,int> > filter(int n,vector<pair<int,int> > &seg) 861 { 862 vector<pair<int,int> > now; 863 for(auto &t:seg) 864 { 865 t.second=(t.second+n-1)%n; 866 int l=t.first,r=t.second; 867 if(l<=r) 868 { 869 now.push_back(make_pair(l,-r)); 870 now.push_back(make_pair(l+n,-(r+n))); 871 } 872 else now.push_back(make_pair(l,-(r+n))); 873 } 874 sort(now.begin(),now.end()); 875 vector<pair<int,int> > stk; 876 for(auto &t:now) 877 { 878 while(!stk.empty() && stk.back().second<=t.second) 879 stk.pop_back(); 880 stk.push_back(t); 881 } 882 vector<pair<int,int> > res; 883 for(auto &t:stk)if(t.first<n) 884 res.push_back(make_pair(t.first,-t.second)); 885 return res; 886 } 887 int go[MAXN<<1][DEP]; 888 int cal(int n,vector<pair<int,int> > &seg) 889 { 890 seg=filter(n,seg); 891 int m=(int)seg.size(); 892 if(m<2)return m; 893 for(int i=0;i<m;i++) 894 { 895 int l=seg[i].first,r=seg[i].second; 896 seg.push_back(make_pair(l+n,r+n)); 897 } 898 for(int i=0;i<2*m;i++) 899 go[i][0]=lower_bound(seg.begin(),seg.end(),make_pair(seg[i].second+1,0))-seg.begin(); 900 go[2*m][0]=2*m; 901 for(int j=1;j<DEP;j++) 902 for(int i=0;i<=2*m;i++) 903 go[i][j]=go[go[i][j-1]][j-1]; 904 int res=m; 905 for(int i=0;i<m;i++) 906 { 907 int t=i,cnt=0; 908 for(int j=DEP-1;j>=0;j--) 909 if(go[t][j]<i+m) 910 t=go[t][j],cnt+=(1<<j); 911 if(res>cnt+1)res=cnt+1; 912 } 913 return res; 914 } 915 916 const db PI=acos(-1.0); 917 ll x[MAXN],y[MAXN]; 918 db dis[MAXN],ang[MAXN],angl[MAXN],angr[MAXN],anga[MAXN<<1]; 919 920 bool check(int n,int m,db r) 921 { 922 for(int i=0;i<n;i++) 923 { 924 db t=acos(min(1.0L,r/dis[i])); 925 angl[i]=ang[i]-t,angr[i]=ang[i]+t; 926 if(angl[i]<0)angl[i]+=2*PI; 927 if(angr[i]>=2*PI)angr[i]-=2*PI; 928 anga[i<<1]=angl[i],anga[i<<1|1]=angr[i]; 929 } 930 sort(anga,anga+2*n); 931 int k=unique(anga,anga+2*n)-anga; 932 vector<pair<int,int> > seg; 933 for(int i=0;i<n;i++) 934 { 935 int l=lower_bound(anga,anga+k,angl[i])-anga; 936 int r=lower_bound(anga,anga+k,angr[i])-anga; 937 seg.push_back({l,r}); 938 } 939 return cal(k,seg)<=m; 940 } 941 942 int main() 943 { 944 int n,m; 945 scanf("%d%d",&n,&m); 946 for(int i=0;i<n;i++) 947 scanf("%lld%lld",&x[i],&y[i]); 948 db md=1e7; 949 for(int i=0;i<n;i++) 950 { 951 dis[i]=sqrtl(x[i]*x[i]+y[i]*y[i]); 952 ang[i]=atan2(y[i],x[i]); 953 if(ang[i]<0)ang[i]+=2*PI; 954 md=min(md,dis[i]); 955 } 956 if(md<1e-7)return 0*printf("%.12Lf\n",0.0L); 957 db tl=0,tr=1; 958 while(tr<md && check(n,m,tr)) 959 tl=tr,tr=min(md,2*tr); 960 for(int _=0;_<25;_++) 961 { 962 db tm=(tl+tr)/2; 963 if(check(n,m,tm))tl=tm; 964 else tr=tm; 965 } 966 return 0*printf("%.12Lf\n",(tl+tr)/2); 967 } 968 ``` 969 970 [1190F - Tokitsukaze и степени](/contest/1190/problem/F "Codeforces Round 573 (Div. 1)") 971 972 Idea: [skywalkert](/profile/skywalkert "Гроссмейстер skywalkert") 973 974 **Tutorial** 975 976 Firstly, let me briefly review this problem for you. Given integers $n$, $m$ and $p$ ($n \gt 0$, $m \gt 1$, $p \neq 0$), we denote $S = \lbrace x | x \in \mathbb{Z}, 0 \leq x \lt m, \gcd(m, x) = 1 \rbrace$ and $T = \lbrace p^e \bmod m | e \in \mathbb{Z}, e \geq 0 \rbrace$, where $\gcd(m, x)$ means the greatest common divisor of $m$ and $x$, and you are asked to pick up $n$ distinct integers from $(S - T)$, the set of elements in $S$ but not in $T$, or report that it is unachievable. Besides, there is an additional restriction, $m = q^k$ for a prime number $q$ and a positive integer $k$. 977 978 It is not difficult to show $|S|$, the size of $S$, equals to $\varphi(m) = m (1 - \frac{1}{q})$. When $\gcd(m, p) \gt 1$, there is only one element $p^0 \bmod m = 1$ in $T$ which is coprime to $m$, so in that case, $|S - T| = \varphi(m) - 1$. To output a solution, you can just enumerate the smallest integers and skip the integer $1$ and any multiples of $q$. In this process, you won't need to enumerate more than $(2 n + 1)$ integers, because $\frac{n}{1 - \frac{1}{q}} + 1 \leq 2 n + 1$. 979 980 When $\gcd(m, p) = 1$, we can observe that $T \subseteq S$. Let $|T|$ be $\lambda$, and we may conclude from Euler's totient theorem that $\lambda \leq \varphi(m)$, and even $\lambda | \varphi(m)$. When $n \gt \varphi(m) - \lambda$, there is no solution, so we need to calculate $\lambda$ in order to determine the existence of solutions. 981 982 To calculate $\lambda$, you can just enumerate all the divisors of $\varphi(m)$ and check them using *Fast Power Algorithm*, because the number of divisors is not too large due to the restrictions. Alternatively, you can do it more advanced and check more efficiently like the following. 983 984 ``` 985 lambda = phi(m) 986 for each x in prime factors of phi(m) : 987 if pow(p, lambda / x, m) == 1 : 988 lambda = lambda / x 989 ``` 990 991 The above approach requires $\mathcal{O}(\log \varphi(m))$ calls of *Fast Power Algorithm*. It is used more regularly when searching a random primitive root in modulo some integer. 992 993 When implementing *Fast Power Algorithm*, you may notice an issue that the modular multiplication may not be easy to code, when the 128-bit integer operations are not directly provided on this platform. In a precise way, you can implement another like *Fast Multiplying Algorithm*, though it is a bit slow. But if you believe you are lucky enough and you prefer using C/C++, you can try the following code in a convenient way. 994 995 ``` 996 typedef long long LL; 997 typedef long double LD; 998 LL mod_mul(LL x, LL y, LL mod) { // 0 <= x, y < mod 999 LL ret = x * y - (LL)((LD)x * y / mod + 0.5) * mod; 1000 return ret < 0 ? ret + mod : ret; 1001 } 1002 ``` 1003 1004 No matter what approach you used, the factorization of $(q - 1)$ is inevitable, so the problem requires you to factorize a relatively large number (less than $10^{18}$) a bit quickly. For example, you can use *Pollard's Rho Algorithm* with *Miller-Rabin Primality Test*. By *Birthday Paradox*, which is a heuristic claim, when $x$ is not a prime, *Pollard's Rho Algorithm* can split $x$ into $u \cdot v$ in $\mathcal{O}(\sqrt{\min(u, v)}) = \mathcal{O}(x^{1 / 4})$ iterations. By the way, you can obtain $q$ from $m$ by enumerating possible $k$ from large to small, instead of factorization. 1005 1006 Let's go back to the case that $\gcd(m, p) = 1$ and $n \leq \varphi(m) - \lambda$. When any solution exists, we can observe that $\varphi(m) - \lambda \geq \frac{\varphi(m)}{2}$, so there may exist some solutions based on random distribution. That is, if you are able to check whether an integer is in $T$ or not, you can roughly pick $2 n$ integers in $S$ and check them. One approach is like the mechanism built in the problem checker, but as space is limited, I would not expend it at here. One thing you should be aware of is that you can't pick them without checking, as the probability of failure may be so large, like $\frac{1}{2}$. Moreover, you can't use *Baby-Step-Giant-Step algorithm* since its time complexity $\mathcal{O}(\sqrt{n m})$ is too slow. 1007 1008 If there exists at least one primitive root in modulo $m$, then we can construct the output integers. Since a primitive root $g$ can represent $S$ as $\lbrace g^e \bmod m | e \in \mathbb{Z}, 0 \leq e \lt \varphi(m) \rbrace$, we can reduce the problem into something about modular equation that only concerns the exponents. As the number of primitive root in modulo $m$ is $\varphi(\varphi(m))$, if the root exists, we can get a random primitive root easily. Now let's assume we find a primitive root $g$ and $p \equiv g^u \pmod{m}$. An integer $(g^v \bmod m)$ is in $T$ if and only if the equation $e u \equiv v \pmod{\varphi(m)}$ has a solution of $e$. It is easy to show, when $\gcd(\varphi(m), u) | v$, a solution of $e$ always exists, so the construction is quite straightforward. 1009 1010 The only case we left is when no primitive root exists in modulo $m$, which occurs when $m = 2^k$, $k \geq 3$. In this case, we cannot represent all the elements in $S$ as non-negative integer powers of one specific number, but we can find a pseudo-primitive root $g'$ to use its powers to represent all the elements in the form of $(4 t + 1)$ in $S$ (as the group $(S, \times_m)$, also known as $(\mathbb{Z}/m\mathbb{Z})^{\times}$, is isomorphic to a direct product of cyclic groups, $\mathrm{C}_2 \times \mathrm{C}_{2^{k - 2}}$). Besides, $\lbrace m - ({g'}^{e} \bmod m) | e \in \mathbb{Z}, 0 \leq e \lt 2^{k - 2} \rbrace$ can represent the rest numbers (in the form of $(4 t + 3)$) in $S$. As the product of two integers in the form of $(4 t + 3)$ is in the form of $(4 t + 1)$, we can discuss the parity of $e$ in expression $(p^e \bmod m)$ and check if an integer is in $T$, so the construction could work after a little modification. By the way, there exist many different construction methods for this case. 1011 1012 In summary, to solve this problem, we need to factorize $\varphi(m)$, calculate the order of $p$ in modulo $m$, find a primitive root $g$ (or a pseudo-primitive root $g'$) in modulo $m$ and enumerate some small integers (values or exponents) to construct a solution. 1013 1014 **Time complexity: $\mathcal{O}((m^{1 / 4} + n) M(m))$, where $M(m)$ means the cost of one multiplication modulo $m$.** Some slow solutions are accepted as well. 1015 1016 **Solution (by skywalkert)** 1017 1018 ``` 1019 #include <bits/stdc++.h> 1020 using namespace std; 1021 1022 typedef long long LL; 1023 inline LL mod_add(LL x, LL y, LL mod) { 1024 return (x += y) < mod ? x : x - mod; 1025 } 1026 inline LL mod_mul(LL x, LL y, LL mod) { 1027 const int BLEN = __builtin_clzll(mod) - 1; 1028 const LL BMSK = (1LL << BLEN) - 1; 1029 LL ret = 0; 1030 if(x < y) 1031 swap(x, y); 1032 while(y > 0) { 1033 ret += x * (y & BMSK); 1034 ret = ret < mod ? ret : ret % mod; 1035 y >>= BLEN; 1036 x <<= BLEN; 1037 x = x < mod ? x : x % mod; 1038 } 1039 return ret; 1040 /* 1041 typedef long double LD; 1042 LL ret = x * y - (LL)((LD)x * y / mod + 0.5) * mod; 1043 return ret < 0 ? ret + mod : ret; 1044 */ 1045 } 1046 inline LL mod_pow(LL x, LL k, LL mod) { 1047 LL ret = mod > 1 ? 1 : 0; 1048 for( ; k > 0; k >>= 1, x = mod_mul(x, x, mod)) 1049 if(k & 1) 1050 ret = mod_mul(ret, x, mod); 1051 return ret; 1052 } 1053 inline LL int_pow(LL x, int k, LL upp) { 1054 LL ret = 1, lim = (++upp) / x; 1055 for( ; k > 0; --k) { 1056 if(ret > lim) 1057 return upp; 1058 ret *= x; 1059 } 1060 return ret; 1061 } 1062 inline bool miller_rabin(LL n) { 1063 if(n == 2) 1064 return 1; 1065 if(n < 2 || !(n & 1)) 1066 return 0; 1067 LL s, r; 1068 for(s = 0, r = n - 1; !(r & 1); r >>= 1, ++s); 1069 static const int ptot = 12, pr[ptot] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}; 1070 for(int p : pr) { 1071 if(p >= n) 1072 break; 1073 LL cur = 1, nxt = p; 1074 for(LL k = r; k > 0; k >>= 1, nxt = mod_mul(nxt, nxt, n)) 1075 if(k & 1) 1076 cur = mod_mul(cur, nxt, n); 1077 for(int i = 0; i < s; ++i) { 1078 nxt = mod_mul(cur, cur, n); 1079 if(nxt == 1 && cur != 1 && cur != n - 1) 1080 return 0; 1081 cur = nxt; 1082 } 1083 if(cur != 1) 1084 return 0; 1085 } 1086 return 1; 1087 } 1088 inline LL pollard_rho(LL n) { 1089 static mt19937_64 rnd(996); 1090 while(1) { 1091 LL x = rnd() % (n - 3) + 2, y = x, c = rnd() % n, tim = 0, prd = 1; 1092 for(LL i = 1, stp = 2; ; ++i) { 1093 if(i == stp) { 1094 y = x; 1095 stp <<= 1; 1096 } 1097 if((x = mod_add(mod_mul(x, x, n), c, n)) == y) 1098 break; 1099 LL tmp = prd; 1100 if((prd = mod_mul(prd, abs(y - x), n)) == 0) 1101 return __gcd(tmp, n); 1102 static const int maxt = 100; 1103 if((++tim) < maxt) 1104 continue; 1105 if((prd = __gcd(prd, n)) > 1) 1106 return prd; 1107 tim = 0; 1108 } 1109 if(tim > 0 && (prd = __gcd(prd, n)) > 1) 1110 return prd; 1111 } 1112 assert(0); 1113 } 1114 inline vector<pair<LL, LL> > factorize(LL n) { 1115 vector<LL> vec; 1116 queue<LL> que; 1117 que.push(n); 1118 while(!que.empty()) { 1119 LL x = que.front(); 1120 que.pop(); 1121 for(LL y : vec) 1122 for( ; x % y == 0; x /= y, vec.push_back(y)); 1123 if(x == 1) 1124 continue; 1125 if(miller_rabin(x)) { 1126 vec.push_back(x); 1127 } else { 1128 LL y = pollard_rho(x); 1129 que.push(y); 1130 que.push(x / y); 1131 } 1132 } 1133 sort(vec.begin(), vec.end()); 1134 vector<pair<LL, LL> > ret; 1135 for(LL x : vec) 1136 if(!ret.empty() && ret.back().first == x) { 1137 ++ret.back().second; 1138 } else { 1139 ret.push_back(make_pair(x, 1LL)); 1140 } 1141 return ret; 1142 } 1143 1144 const int maxn = (int)5e5 + 1, maxe = 60; 1145 int n; 1146 LL m, sp, pr, ex, phi, ord, gen; 1147 void init() { 1148 scanf("%d%lld%lld", &n, &m, &sp); 1149 for(ex = maxe - 1; ex >= 1; --ex) { 1150 if(m < (1LL << ex)) 1151 continue; 1152 LL low = 2, upp; 1153 for(upp = low << 1; int_pow(upp, ex, m) <= m; upp <<= 1); 1154 while(low < upp) { 1155 LL mid = (low + upp + 1) >> 1; 1156 if(int_pow(mid, ex, m) <= m) { 1157 low = mid; 1158 } else { 1159 upp = mid - 1; 1160 } 1161 } 1162 if(int_pow(low, ex, m) == m) { 1163 pr = low; 1164 break; 1165 } 1166 } 1167 assert(ex >= 1 && miller_rabin(pr)); 1168 phi = m - m / pr; 1169 if(sp % pr == 0) { 1170 ord = gen = -1; 1171 return; 1172 } 1173 ord = phi; 1174 vector<pair<LL, LL> > vec = factorize(pr - 1); 1175 if(ex > 1) 1176 vec.push_back(make_pair(pr, ex - 1)); 1177 for(pair<LL, LL> it : vec) 1178 for( ; it.second > 0 && mod_pow(sp, ord / it.first, m) == 1; --it.second, ord /= it.first); 1179 if(pr == 2 && m >= 8) { 1180 assert((sp & 3) != 3 || !(ord & 1)); 1181 LL half_phi = phi / 2; 1182 for(gen = 1; gen < m; gen += 4) { 1183 bool chk = mod_pow(gen, half_phi, m) == 1; 1184 for(pair<LL, LL> it : vec) 1185 chk &= mod_pow(gen, half_phi / it.first, m) != 1; 1186 if(chk) 1187 break; 1188 } 1189 } else { 1190 for(gen = 0; gen < m; ++gen) { 1191 bool chk = mod_pow(gen, phi, m) == 1; 1192 for(pair<LL, LL> it : vec) 1193 chk &= mod_pow(gen, phi / it.first, m) != 1; 1194 if(chk) 1195 break; 1196 } 1197 } 1198 } 1199 void solve() { 1200 if(n > phi - abs(ord)) { 1201 puts("-1"); 1202 return; 1203 } 1204 if(ord == -1) { 1205 LL val = 1; 1206 for(int i = 1; i <= n; ++i) { 1207 for(++val; val < m && val % pr == 0; ++val); 1208 assert(val < m); 1209 printf("%lld%c", val, " \n"[i == n]); 1210 } 1211 return; 1212 } 1213 if(pr == 2 && m >= 8 && (sp & 3) == 3) { 1214 LL upp = phi / 2, stp = upp / (ord / 2); 1215 for(LL e = 0, u = 1, v = sp; e < upp && n > 0; ++e, u = mod_mul(u, gen, m), v = mod_mul(v, gen, m)) 1216 if(e % stp > 0) { 1217 printf("%lld%c", u, " \n"[!(--n)]); 1218 if(n > 0) 1219 printf("%lld%c", v, " \n"[!(--n)]); 1220 } 1221 } else { 1222 LL upp = pr == 2 ? phi / 2 : phi, stp = upp / ord; 1223 for(LL e = 0, v = 1; e < upp && n > 0; ++e, v = mod_mul(v, gen, m)) { 1224 if(e % stp > 0) 1225 printf("%lld%c", v, " \n"[!(--n)]); 1226 if(n > 0 && pr == 2) 1227 printf("%lld%c", m - v, " \n"[!(--n)]); 1228 } 1229 } 1230 assert(n == 0); 1231 } 1232 int main() { 1233 init(); 1234 solve(); 1235 return 0; 1236 } 1237 ``` 1238 1239 **Solution (by quailty)** 1240 1241 ``` 1242 #include<bits/stdc++.h> 1243 using namespace std; 1244 1245 typedef long long ll; 1246 typedef unsigned long long ull; 1247 1248 inline ll mul_mod(ll a, ll b, ll m) 1249 { 1250 a=(a%m+m)%m,b=(b%m+m)%m; 1251 return ((a*b-(ll)(1.0L*a/m*b+0.5L)*m)%m+m)%m; 1252 } 1253 inline ll pow_mod(ll a,ll k,ll m) 1254 { 1255 ll res=1; 1256 while(k) 1257 { 1258 if(k&1)res=mul_mod(res,a,m); 1259 a=mul_mod(a,a,m); 1260 k>>=1; 1261 } 1262 return res; 1263 } 1264 1265 bool strong_pseudo_primetest(ll n,int b) 1266 { 1267 ll n2=n-1,res; 1268 int s=0; 1269 while(n2%2==0)n2>>=1,s++; 1270 res=pow_mod(b,n2,n); 1271 if((res==1)|| (res==n-1))return 1; 1272 s--; 1273 while(s>=0) 1274 { 1275 res=mul_mod(res,res,n); 1276 if(res==n-1)return 1; 1277 s--; 1278 } 1279 return 0; 1280 } 1281 bool is_prime(ll n) 1282 { 1283 static ll testNum[]={2,3,5,7,11,13,17,19,23,29,31,37}; 1284 static ll lim[]={4,0,1373653LL,25326001LL,25000000000LL,2152302898747LL,3474749660383LL,341550071728321LL,0,0,0,0}; 1285 if(n<2 || n==3215031751LL)return 0; 1286 for(int i=0;i<12;i++) 1287 { 1288 if(n<lim[i])return 1; 1289 if(!strong_pseudo_primetest(n,testNum[i]))return 0; 1290 } 1291 return 1; 1292 } 1293 1294 inline ll func(ll x,ll n) 1295 { 1296 return (mul_mod(x,x,n)+1)%n; 1297 } 1298 ll pollard(ll n) 1299 { 1300 if(is_prime(n))return n; 1301 if(~n&1)return 2; 1302 for(int i=1;i<20;i++) 1303 { 1304 ll x=i,y=func(x,n),p=__gcd(y-x,n); 1305 while(p==1)x=func(x,n),y=func(func(y,n),n),p=__gcd((y-x+n)%n,n)%n; 1306 if(p==0 || p==n)continue; 1307 return p; 1308 } 1309 return 1; 1310 } 1311 vector<ll> factor(ll n) 1312 { 1313 if(n==1)return {}; 1314 ll x=pollard(n); 1315 if(x==n)return {n}; 1316 vector<ll> res=factor(x); 1317 vector<ll> t=factor(n/x); 1318 res.insert(res.end(),t.begin(),t.end()); 1319 return res; 1320 } 1321 1322 vector<ll> solve_easy(int n,ll m) 1323 { 1324 vector<ll> res; 1325 for(ll i=2;i<m && (int)res.size()<n;i++) 1326 if(__gcd(i,m)==1)res.push_back(i); 1327 return res; 1328 } 1329 1330 bool dfs_sol(int i,int k,ull x,ull p,ull t) 1331 { 1332 if(i>k)return 1; 1333 ull mask=(1ULL<<i)-1; 1334 if((t&mask)==(x&mask) && dfs_sol(i+1,k,x,p*p,t))return 1; 1335 if(((t*p)&mask)==(x&mask) && dfs_sol(i+1,k,x,p*p,t*p))return 1; 1336 return 0; 1337 } 1338 vector<ll> solve_even(int n,ll m,ll p,int k)///m=2^k 1339 { 1340 vector<ll> res; 1341 for(ll i=3;i<m && (int)res.size()<n;i+=2) 1342 if(!dfs_sol(3,k,i,p,1))res.push_back(i); 1343 return res; 1344 } 1345 1346 void dfs_fac(int dep,ll val,vector<pair<ll,int> > &pcnt,vector<ll> &fac) 1347 { 1348 if(dep==(int)pcnt.size()) 1349 { 1350 fac.push_back(val); 1351 return; 1352 } 1353 for(int i=0;i<=pcnt[dep].second;i++) 1354 { 1355 dfs_fac(dep+1,val,pcnt,fac); 1356 val*=pcnt[dep].first; 1357 } 1358 } 1359 vector<ll> solve_root(int n,ll m,ll p,vector<ll> pm) 1360 { 1361 ll phi=m/pm[0]*(pm[0]-1); 1362 vector<ll> pphi=factor(phi); 1363 sort(pphi.begin(),pphi.end()); 1364 vector<pair<ll,int> > pcnt; 1365 for(int i=0,j=0;i<(int)pphi.size();i=j) 1366 { 1367 while(j<(int)pphi.size() && pphi[i]==pphi[j])j++; 1368 pcnt.push_back({pphi[i],j-i}); 1369 } 1370 pphi.erase(unique(pphi.begin(),pphi.end()),pphi.end()); 1371 vector<ll> fac; 1372 dfs_fac(0,1,pcnt,fac); 1373 ll pmr=0; 1374 while(++pmr) 1375 { 1376 bool isok=(__gcd(pmr,m)==1); 1377 for(int i=0;i<(int)pphi.size() && isok;i++) 1378 isok&=(pow_mod(pmr,phi/pphi[i],m)>1); 1379 if(isok)break; 1380 } 1381 ll len=phi; 1382 for(auto &t:fac) 1383 if(pow_mod(p,t,m)==1) 1384 len=min(len,t); 1385 if(len==phi)return {}; 1386 vector<ll> res; 1387 for(ll i=0;i<phi && (int)res.size()<n;i++) 1388 if(i%(phi/len))res.push_back(pow_mod(pmr,i,m)); 1389 return res; 1390 } 1391 1392 int main() 1393 { 1394 int n; 1395 ll m,p; 1396 scanf("%d%lld%lld",&n,&m,&p); 1397 vector<ll> res; 1398 if(__gcd(m,p)>1) 1399 res=solve_easy(n,m); 1400 else 1401 { 1402 vector<ll> pm=factor(m); 1403 if(pm[0]==2 && (int)pm.size()>2) 1404 res=solve_even(n,m,p,(int)pm.size()); 1405 else 1406 res=solve_root(n,m,p,pm); 1407 } 1408 if((int)res.size()<n) 1409 printf("-1\n"); 1410 else for(int i=0;i<n;i++) 1411 printf("%lld%c",res[i]," \n"[i==n-1]); 1412 return 0; 1413 } 1414 ```