codeforces-scrape

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

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 ```