codeforces-scrape

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

2082.md (49746B)


      1 Source: https://codeforces.com/blog/entry/140702
      2 
      3 Sorry for the late editorial. Our problem setters were so exhausted with the offline competition yesterday that they really need some good rest.
      4 
      5 Despite the unexpected and unpleasant incidents that occurred, we are truly surprised and grateful that so many of you still participated in this competition! We sincerely hope you enjoyed it!
      6 
      7 (Gratitude for all you guys from [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_"): I felt so heartbroken when I heard about the unexpected issues, but seeing so many people in the comments comforting us, sharing thoughtful and positive messages that showed genuine empathy, and continuing to fully support our competition even after the wasted time, I was deeply moved. Thank you all! Codeforces truly embodies such a positive and uplifting community spirit!)
      8 
      9 [2082A - Binary Matrix](/contest/2082/problem/A "Codeforces Round 1010 (Div. 2, Unrated)")   
     10  Idea: [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_")
     11 
     12 **Hint**
     13 
     14 Do we really have to consider the problem on the whole matrix?
     15 
     16 **Solution**
     17 
     18 Let $r$ be the number of rows where the bitwise XOR of all the numbers in it is $1$, and $c$ be the number of columns where the bitwise XOR of all the numbers in it is $1$. Our goal is to make both $r$ and $c$ zero.
     19 
     20 When we change an element in the matrix, both $r$ and $c$ change by exactly one. Thus, it's not hard to see that the answer is $\max (r,c)$.
     21 
     22 The time complexity is $O(\sum nm)$.
     23 
     24 **Code**
     25 
     26 ```
     27 #include<bits/stdc++.h>
     28 using namespace std;
     29 typedef long long ll;
     30 ll t,n,m,r,c;
     31 char s[1009];
     32 bool a[1009][1009];
     33 inline ll read(){
     34 	ll s = 0,w = 1;
     35 	char ch = getchar();
     36 	while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
     37 	while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
     38 	return s * w;
     39 }
     40 int main(){
     41 	t = read();
     42 	while (t --){
     43 		n = read(),m = read(),r = c = 0;
     44 		for (ll i = 1;i <= n;i += 1){
     45 			scanf("%s",s + 1);
     46 			for (ll j = 1;j <= m;j += 1) a[i][j] = s[j] - '0';
     47 		}
     48 		for (ll i = 1;i <= n;i += 1){
     49 			bool sum = 0;
     50 			for (ll j = 1;j <= m;j += 1) sum ^= a[i][j];
     51 			if (sum) r += 1;
     52 		}
     53 		for (ll j = 1;j <= m;j += 1){
     54 			bool sum = 0;
     55 			for (ll i = 1;i <= n;i += 1) sum ^= a[i][j];
     56 			if (sum) c += 1;
     57 		}
     58 		printf("%lld\n",max(r,c));
     59 	}
     60 	return 0;
     61 }
     62 ```
     63 
     64 [2082B - Floor or Ceil](/contest/2082/problem/B "Codeforces Round 1010 (Div. 2, Unrated)")   
     65  Idea: [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_"), [FairyWinx](/profile/FairyWinx "Grandmaster FairyWinx")
     66 
     67 **Hint 1**
     68 
     69 Consider $x$ in binary form.
     70 
     71 **Hint 2**
     72 
     73 What are all possible values of $x$ after $n+m$ operations?
     74 
     75 **Solution**
     76 
     77 Let's consider how to find the maximum value first.
     78 
     79 Consider $x$ in binary form. Let the number formed by the last $n+m$ bits of $x$ be denoted as $r$, and the remaining higher bits form the number $l$ (for instance, if $x=12=(1100)_2$, $n=1$, $m=2$, then $l=1=(1)_2$, $r=4=(100)_2$), then the final value of $x$ after $n+m$ operations will be either $l$ or $l+1$, depending on whether a carry-over occurs in $r$ during the last operation.
     80 
     81 If there are no $1$s in the higher $m$ bits of $r$, then the carry-over in $r$ during the last operation can never occur (operating on some small tests may give you a better understanding). Otherwise, we can choose to perform $n$ floor operations first followed by $m$ ceil operations, which can guarantee a carry-over in $r$ during the last operation.
     82 
     83 This demonstrates that performing $n$ floor operations first followed by $m$ ceil operations will always yield the maximum value. Similarly, performing $m$ ceil operations first followed by $n$ floor operations will always produce the minimum value. We can simply simulate these operations because after $O(\log x)$ same operations, $x$ will remain unchanged.
     84 
     85 The time complexity is $O(T\log x)$.
     86 
     87 **Code**
     88 
     89 ```
     90 #include<bits/stdc++.h>
     91 using namespace std;
     92 typedef long long ll;
     93 ll t,x,n,m;
     94 inline ll read(){
     95 	ll s = 0,w = 1;
     96 	char ch = getchar();
     97 	while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
     98 	while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
     99 	return s * w;
    100 }
    101 ll F(ll x,ll n){
    102 	while (n --){
    103 		if (!x) return x;
    104 		x = (x >> 1);
    105 	}
    106 	return x;
    107 }
    108 ll C(ll x,ll n){
    109 	while (n --){
    110 		if (x <= 1) return x;
    111 		x = ((x + 1) >> 1);
    112 	}
    113 	return x;
    114 }
    115 int main(){
    116 	t = read();
    117 	while (t --){
    118 		x = read(),n = read(),m = read();
    119 		printf("%lld %lld\n",F(C(x,m),n),C(F(x,n),m));
    120 	}
    121 	return 0;
    122 }
    123 ```
    124 
    125 [2081A - Math Division](/contest/2081/problem/A "Codeforces Round 1010 (Div. 1, Unrated)")   
    126  Idea: [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_")
    127 
    128 **Hint 1**
    129 
    130 Consider $x$ in binary form.
    131 
    132 **Hint 2**
    133 
    134 What are all possible numbers of operations to make $x$ equal to $1$?
    135 
    136 **Hint 3**
    137 
    138 Consider using dynamic programming to calculate the answer.
    139 
    140 **Solution**
    141 
    142 Similar to the previous problem, the possible number of operations can only be $n-1$ or $n$, depending on whether a carry-over occurs in $x$ during the $(n-1)$ -th operation.
    143 
    144 We can use dynamic programming to compute the probability of a carry-over occurring during the $(n-1)$ -th operation.
    145 
    146 Let $f_i$ denote the probability of a carry-over occurring at the $i$ -th least significant bit. The recurrence relation is:
    147 
    148 $ f_i = \begin{cases} \dfrac{1}{2} \times f_{i-1} & x_i = 0 \\ \dfrac{1}{2} \times (1 - f_{i-1}) + f_{i-1} & x_i = 1 \end{cases} $
    149 
    150 The final answer is given by $n-1+f_{n-1}$.
    151 
    152 The time complexity is $O(\sum n)$.
    153 
    154 **Code**
    155 
    156 ```
    157 #include<bits/stdc++.h>
    158 using namespace std;
    159 typedef long long ll;
    160 const ll inv2 = 5e8 + 4,mod = 1e9 + 7;
    161 ll t,n;
    162 char s[1000009];
    163 inline ll read(){
    164 	ll s = 0,w = 1;
    165 	char ch = getchar();
    166 	while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
    167 	while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
    168 	return s * w;
    169 }
    170 int main(){
    171 	t = read();
    172 	while (t --){
    173 		n = read(),scanf("%s",s + 1);
    174 		ll ans = 0;
    175 		for (ll i = n;i > 1;i -= 1) ans = (ans + (s[i] == '1')) * inv2 % mod;
    176 		printf("%lld\n",(n - 1 + ans) % mod);
    177 	}
    178 	return 0;
    179 }
    180 ```
    181 
    182 [2081B - Balancing](/contest/2081/problem/B "Codeforces Round 1010 (Div. 1, Unrated)")   
    183  Idea: [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_")
    184 
    185 **Hint 1**
    186 
    187 Let's only consider the comparison between adjacent pairs first. Call a pair $(a_i,a_{i+1})$ an inversion pair if $a_i \gt a_{i+1}$.
    188 
    189 In each operation, how can the number of inversion pairs change?
    190 
    191 **Hint 2**
    192 
    193 Under what circumstances can we decrease the maximum number of inversion pairs in every operation?
    194 
    195 **Solution**
    196 
    197 Let's only consider the comparison between adjacent pairs first. Call a pair $(a_i,a_{i+1})$ an inversion pair if $a_i \gt a_{i+1}$. Our goal is to decrease the number of inversion pairs to zero.
    198 
    199 If we choose to replace $a_l,a_{l+1},\ldots,a_r$, only the comparison between $(a_{l-1},a_l)$ and $(a_{r},a_{r+1})$ can change, which means we can eliminate at most two inversion pairs in one operation. Let $s$ be the number of inversion pairs in $a_1,a_2,\ldots,a_n$, then a lower bound of the answer is $l=\left\lceil\dfrac{s}{2}\right\rceil$.
    200 
    201 #### **Case 1: $s \gt 0$ and $2\mid s$**
    202 
    203 In order to obtain the lower bound $l$, each operation must eliminate exactly two inversion pairs. This necessitates that we cannot alter any numbers before the first element $a_{p_1}$ of the first inversion pair or after the second element $a_{p_2}$ of the last inversion pair. (Why?)
    204 
    205 An intuitive idea is that the difference between $a_{p_1}$ and $a_{p_2}$ should be as large as possible (more precisely, $a_{p_2} - a_{p_1} \geq p_2 - p_1$), so that a strictly increasing sequence can be "accommodated" between them. It is not difficult to constructively prove by recursion that this condition is both necessary and sufficient.
    206 
    207 In other words, when $a_{p_2} - a_{p_1} \geq p_2 - p_1$, the answer is $l$; otherwise, an additional operation is required, making the answer $l+1$.
    208 
    209 #### **Case 2: $s=0$ or $2\not\mid s$**
    210 
    211 It's not difficult to prove that the answer in this case is $l$. (Why?)
    212 
    213 The time complexity is $O(\sum n)$.
    214 
    215 **Code**
    216 
    217 ```
    218 #include<bits/stdc++.h>
    219 using namespace std;
    220 typedef long long ll;
    221 ll t,n,a[200009];
    222 inline ll read(){
    223 	ll s = 0,w = 1;
    224 	char ch = getchar();
    225 	while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
    226 	while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
    227 	return s * w;
    228 }
    229 int main(){
    230 	t = read();
    231 	while (t --){
    232 		n = read();
    233 		for (ll i = 1;i <= n;i += 1) a[i] = read();
    234 		ll ans = 0,pos1 = 0,pos2 = 0;
    235 		for (ll i = 1;i < n;i += 1) if (a[i] > a[i + 1]){
    236 			ans += 1,pos2 = i + 1;
    237 			if (!pos1) pos1 = i;
    238 		}
    239 		if ((ans & 1) || (pos1 && a[pos2] - a[pos1] < pos2 - pos1)) printf("%lld\n",(ans >> 1) + 1);
    240 		else printf("%lld\n",ans >> 1);
    241 	}
    242 	return 0;
    243 }
    244 ```
    245 
    246 [2081C - Quaternary Matrix](/contest/2081/problem/C "Codeforces Round 1010 (Div. 1, Unrated)")   
    247  Idea: [Ecrade_](/profile/Ecrade_ "Grandmaster Ecrade_")
    248 
    249 **Hint 1**
    250 
    251 Do we really have to consider the problem on the whole matrix?
    252 
    253 **Hint 2**
    254 
    255 Use greedy algorithm and guess some possible conclusions. Can you prove them (or construct some counterexamples) ?
    256 
    257 **Solution**
    258 
    259 The problem can be rephrased as follows: Let the XOR sum of each row be $ r_1, r_2, \ldots, r_n $, and the XOR sum of each column be $ c_1, c_2, \ldots, c_m $. In each operation, we can choose any $ 1 \le i \le n $, $ 1 \le j \le m $, and $ 0 \le x \le 3 $, then let $ r_i \leftarrow r_i \oplus x $ and $ c_j \leftarrow c_j \oplus x $. The goal is to determine the minimum number of operations required to make all $ r_1, r_2, \ldots, r_n $ and $ c_1, c_2, \ldots, c_m $ zero.
    260 
    261 Let $ R_x\ ( 0 \le x \le 3 )$ denote the count of $ x $ in $ r_1, r_2, \ldots, r_n $, and $ C_x $ denote the count of $ x $ in $ c_1, c_2, \ldots, c_m $. A trivial upper bound for the answer is $ s = R_1 + R_2 + R_3 + C_1 + C_2 + C_3 $, which corresponds to the scenario where each operation only zeros out one of $ r_i $ and $ c_j $.
    262 
    263 To reduce the number of operations, we can consider grouping the non-zero elements in $ r_1, \ldots, r_n, c_1, \ldots, c_m $ into disjoint groups where:
    264 
    265 1. The XOR sum of each group is zero.
    266 2. Each group contains at least one element from $ r $ and one from $ c $.
    267 
    268 For such a group, we can reduce the number of operations by one, as there always exists an operation which can zero out both $ r_i $ and $ c_j $. Thus, the goal is to maximize the number of such groups, and the minimum number of operations will be $s - \text{(number of groups formed)}$.
    269 
    270 Define the following group types:
    271 
    272 * $ P_2 $: Groups of the form $(R_1,C_1)$, $(R_2,C_2)$ or $(R_3,C_3)$.
    273 * $ P_3 $: Groups of the form $(R_1,R_2,C_3)$, $(R_1,C_2,C_3)$, $(R_1,C_2,R_3)$, $(C_1,C_2,R_3)$, $(C_1,R_2,R_3)$ or $(C_1,R_2,C_3)$.
    274 * $ P_4 $: Groups of the form $(R_1,R_1,C_2,C_2)$, $(R_1,R_1,C_3,C_3)$, $(R_2,R_2,C_1,C_1)$, $(R_2,R_2,C_3,C_3)$, $(R_3,R_3,C_1,C_1)$ or $(R_3,R_3,C_2,C_2)$.
    275 
    276 **Conclusion 1:** There exists an optimal solution where all groups are of the form $ P_2 $, $ P_3 $, or $ P_4 $.
    277 
    278 **Brief Proof**
    279 
    280 * Each group must have size at least 2. Groups of size 2 or 3 can only be $ P_2 $ or $ P_3 $.
    281 * Groups of size 4 not conforming to $ P_4 $ (e.g., $ (R_1, R_1, R_1, C_1) $) can be decomposed into at least one $ P_2 $.
    282 * Larger groups can be decomposed into combinations of $ P_2 $, $ P_3 $, and $ P_4 $.
    283 
    284 **Conclusion 2:** There exists an optimal solution where all $ P_3 $ groups share the same structure, and so do all $ P_4 $ groups.
    285 
    286 **Brief Proof**
    287 
    288 * Two different $ P_3 $ groups can be decomposed into at least two $ P_2 $ or at least one $ P_2 $ and one $ P_4 $.
    289 * Two different $ P_4 $ groups can be decomposed into at least two $ P_2 $ or at least two $ P_3 $.
    290 
    291 **Conclusion 3:** There exists an optimal solution where the elements in $ P_4 $ groups are a subset of those in $ P_3 $ groups (e.g., if $ P_3 $ is $ (R_1, R_2, C_3) $, then $ P_4 $ can only be $ (R_1, R_1, C_3, C_3) $ or $ (R_2, R_2, C_3, C_3) $). The proof is analogous to Conclusion 2 and is left as an exercise.
    292 
    293 Based on these conclusions, the optimal strategy is: first form as many $P_2$ groups as possible; then form as many $P_3$ groups as possible from the remaining elements; then form as many $P_4$ groups as possible from the remaining elements.
    294 
    295 After grouping, each group can be zeroed out with one less operation. Note that the remaining ungrouped elements require individual operations.
    296 
    297 The time complexity is $O(\sum nm)$.
    298 
    299 **Code**
    300 
    301 ```
    302 #include<bits/stdc++.h>
    303 using namespace std;
    304 typedef long long ll;
    305 ll t,n,m,a[1009][1009];
    306 char s[1009];
    307 vector <ll> row[4],col[4];
    308 inline ll read(){
    309 	ll s = 0,w = 1;
    310 	char ch = getchar();
    311 	while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
    312 	while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
    313 	return s * w;
    314 }
    315 int main(){
    316 	t = read();
    317 	while (t --){
    318 		n = read(),m = read();
    319 		for (ll i = 1;i <= 3;i += 1) row[i].clear(),col[i].clear();
    320 		for (ll i = 1;i <= n;i += 1){
    321 			scanf("%s",s + 1);
    322 			for (ll j = 1;j <= m;j += 1) a[i][j] = s[j] - '0';
    323 		}
    324 		for (ll i = 1;i <= n;i += 1){
    325 			ll sum = 0;
    326 			for (ll j = 1;j <= m;j += 1) sum ^= a[i][j];
    327 			if (sum) row[sum].emplace_back(i);
    328 		}
    329 		for (ll j = 1;j <= m;j += 1){
    330 			ll sum = 0;
    331 			for (ll i = 1;i <= n;i += 1) sum ^= a[i][j];
    332 			if (sum) col[sum].emplace_back(j);
    333 		}
    334 		ll ans = 0;
    335 		for (ll i = 1;i <= 3;i += 1){
    336 			while (row[i].size() && col[i].size()){
    337 				ans += 1;
    338 				a[row[i].back()][col[i].back()] ^= i;
    339 				row[i].pop_back(),col[i].pop_back();
    340 			}
    341 		}
    342 		for (ll i = 1;i <= 3;i += 1){
    343 			ll j = i % 3 + 1,k = j % 3 + 1;
    344 			while (row[i].size() && col[j].size() && col[k].size()){
    345 				ans += 2;
    346 				a[row[i].back()][col[j].back()] ^= j;
    347 				a[row[i].back()][col[k].back()] ^= k;
    348 				row[i].pop_back(),col[j].pop_back(),col[k].pop_back();
    349 			}
    350 			while (col[i].size() && row[j].size() && row[k].size()){
    351 				ans += 2;
    352 				a[row[j].back()][col[i].back()] ^= j;
    353 				a[row[k].back()][col[i].back()] ^= k;
    354 				col[i].pop_back(),row[j].pop_back(),row[k].pop_back();
    355 			}
    356 		}
    357 		for (ll i = 1;i <= 3;i += 1) for (ll j = 1;j <= 3;j += 1) if (i != j){
    358 			while (row[i].size() >= 2 && col[j].size() >= 2){
    359 				ll r1 = row[i].back(); row[i].pop_back();
    360 				ll r2 = row[i].back(); row[i].pop_back();
    361 				ll c1 = col[j].back(); col[j].pop_back();
    362 				ll c2 = col[j].back(); col[j].pop_back();
    363 				ans += 3;
    364 				a[r1][c1] ^= i;
    365 				a[r2][c1] ^= (i ^ j);
    366 				a[r2][c2] ^= j;
    367 			}
    368 		}
    369 		for (ll i = 1;i <= 3;i += 1){
    370 			while (row[i].size()) ans += 1,a[row[i].back()][1] ^= i,row[i].pop_back();
    371 			while (col[i].size()) ans += 1,a[1][col[i].back()] ^= i,col[i].pop_back();
    372 		}
    373 		printf("%lld\n",ans);
    374 		for (ll i = 1;i <= n;i += 1,puts("")) for (ll j = 1;j <= m;j += 1) printf("%lld",a[i][j]);
    375 	}
    376 	return 0;
    377 }
    378 ```
    379 
    380 [2081D - MST in Modulo Graph](/contest/2081/problem/D "Codeforces Round 1010 (Div. 1, Unrated)")   
    381  Idea: [newbiewzs](/profile/newbiewzs "International Master newbiewzs")
    382 
    383 **Hint**
    384 
    385 There are only $O(n\log n)$ edges that are truly useful in the whole graph.
    386 
    387 **Solution**
    388 
    389 First, for vertices with the same weight, they can naturally be treated as a single vertex.
    390 
    391 We observe that in the interval of weights $(kx,(k+1)x)\ (k\ge 1)$, only the smallest $y$ is useful. It is because, if $x \lt y \lt z \lt 2x$, connecting edges $(x,y)$ and $(y,z)$ will always be better than connecting $(x,y)$ and $(x,z)$.
    392 
    393 Therefore, for a vertex with weight $x$, we enumerate $k = x , 2 x , \ldots , \lfloor \frac{n}{x}\rfloor\cdot x$. For each $k$, we connect $x$ to the smallest $y$ that is greater than or equal to $k$.
    394 
    395 It can be proven that this approach guarantees a connected graph (since connecting only the first edge larger than $x$ already forms a connected structure).
    396 
    397 This method generates $O(n\log n)$ edges (due to the harmonic series property). Directly applying Kruskal's algorithm would result in a time complexity of $O(n\log^2 n)$. With radix sort, this can be optimized to $O(n\log n)$.
    398 
    399 **Code**
    400 
    401 ```
    402 #include<iostream>
    403 #include<cstdio>
    404 #include<algorithm>
    405 #include<string.h>
    406 #include<vector>
    407 #include<queue>
    408 #include<map>
    409 #include<ctime>
    410 #include<bitset>
    411 #include<set>
    412 #include<math.h>
    413 //#include<unordered_map>
    414 #define fi first
    415 #define se second
    416 #define mp make_pair
    417 #define pii pair<int,int>
    418 #define pb push_back
    419 #define pil pair<int,long long>
    420 #define pll pair<long long,long long>
    421 #define vi vector<int>
    422 #define vl vector<long long>
    423 #define ci ios::sync_with_stdio(false)
    424 //#define int long long
    425 using namespace std;
    426 typedef long long ll;
    427 typedef unsigned long long ull;
    428 int read(){
    429 	char c=getchar();
    430 	ll x=1,s=0;
    431 	while(c<'0'||c>'9'){
    432 	   if(c=='-')x=-1;c=getchar();
    433 	}
    434 	while(c>='0'&&c<='9'){
    435 	   s=s*10+c-'0';c=getchar();
    436 	}
    437 	return s*x;
    438 }
    439 const int N=5e5+55;
    440 int MAXN=0;
    441 int n,tot,ans,maxx,f[N],siz[N],p[N],bj[N],pre[N],suf[N],pos[N];
    442 struct node{
    443 	int from,to,dis;
    444 }a[N*20];
    445 int cmp(node x,node y){
    446 	return x.dis<y.dis;
    447 }
    448 int find(int x){
    449 	if(f[x]!=x)return f[x]=find(f[x]);
    450 	else return x;
    451 }
    452 void merge(int x,int y){
    453 	x=find(x);y=find(y);
    454 	if(siz[x]<siz[y])swap(x,y);
    455 	siz[x]+=siz[y];
    456 	f[y]=x;
    457 }
    458 int T;
    459 int main(){
    460 	T=read();
    461 	while(T--)
    462 	{
    463 		tot=ans=maxx=0;
    464 		for(int i=1;i<=MAXN;++i)
    465 		{
    466 			f[i]=siz[i]=p[i]=bj[i]=pre[i]=suf[i]=pos[i]=0;
    467 		}
    468 		for(int i=0;i<=MAXN*19;++i)
    469 		a[i].from=a[i].to=a[i].dis=0;
    470 		
    471 		
    472 		
    473 		n=read();
    474 		MAXN=n;
    475 		for(int i=1;i<=n;i++)p[i]=read(),bj[p[i]]=1,maxx=max(maxx,p[i]),MAXN=max(MAXN,p[i]);
    476 		sort(p+1,p+n+1);
    477 		for(int i=1;i<=maxx;i++){
    478 			if(bj[i])pre[i]=i;
    479 			else pre[i]=pre[i-1];
    480 		}
    481 		for(int i=maxx;i>=1;i--){
    482 			if(bj[i])suf[i]=i;
    483 			else suf[i]=suf[i+1];
    484 		}
    485 		for(int i=1;i<=n;i++)pos[p[i]]=i;
    486 		for(int i=1;i<=n;i++){
    487 			if(p[i]==p[i-1]){
    488 				a[++tot]={i,i-1,0};
    489 				continue;
    490 			}
    491 			for(int k=1;k*p[i]<=maxx;k++){
    492 				int tmy=0;
    493 				if(bj[k*p[i]] and k!=1){
    494 					a[++tot]={pos[k*p[i]],i,0};
    495 					continue;
    496 				}
    497 				if(suf[k*p[i]+1]<=(k+1)*p[i])tmy=suf[k*p[i]+1];
    498 				if(!tmy)continue;
    499 				int cost=abs(k*p[i]-tmy);
    500 				a[++tot]={pos[tmy],i,cost};
    501 			}
    502 		}
    503 		sort(a+1,a+tot+1,cmp);
    504 		for(int i=1;i<=n;i++)f[i]=i,siz[i]=1;
    505 		for(int i=1;i<=tot;i++){
    506 			if(find(a[i].from)!=find(a[i].to)){
    507 				merge(a[i].from,a[i].to);
    508 				ans+=a[i].dis;
    509 			}
    510 		}
    511 		cout<<ans<<endl;
    512 	}
    513 	return 0;
    514 }
    515 ```
    516 
    517 [2081E - Quantifier](/contest/2081/problem/E "Codeforces Round 1010 (Div. 1, Unrated)")   
    518  Idea: [chen_03](/profile/chen_03 "Master chen_03")
    519 
    520 **Hint 1**
    521 
    522 Move each chip as deep as possible in descending order of labels. Can we simplify the operations after that?
    523 
    524 **Hint 2**
    525 
    526 Now we only need to move the chips upward and swap adjacent chips with the same color. What can we do after that?
    527 
    528 **Hint 3**
    529 
    530 We can perform dynamic programming (DP) to calculate the numbers. What information do we need to record?
    531 
    532 **Hint 4**
    533 
    534 We need to record the color and the length of the top monochromatic segment. How can we perform the DP in $\mathcal{O}(m^2)$ time complexity?
    535 
    536 **Solution**
    537 
    538 First, in descending order of labels, move each chip to the deepest possible position successively. It can be shown that this allows each chip to reach the theoretically deepest position it can attain. Consequently, every final state can be obtained from this configuration by performing only upward moves of chips and swaps of adjacent chips with the same color.
    539 
    540 Next comes the process of moving chips upward while performing dynamic programming (DP). Let $e_u$ denote the edge from node $u$ to its parent. Assume we have decided the order of all the chips in subtree $u$ (except the ones on $e_u$), and we need to merge them with the original chips on $e_u$. If the bottom chip on $e_u$ shares color with the subtree's top chip, we need to know the length of the subtree's topmost maximal monochromatic contiguous segment to calculate the number of ways to merge the two parts, i.e., if the length of the bottommost segment on $e_u$ is $x$ and the length of the topmost segment of the subtree is $y$, we have $\dbinom{x+y}{x}$ ways to combine them. So we need to record the color and the length of the top segment.
    541 
    542 ![ ](/predownloaded/33/7d/337d8e1dce892c9751c9f28d7dd59bce2c223749.png)
    543 
    544 Let $f_{u,0/1,i}$ denote the number of permutation schemes on $e_u$ after moving all the chips in subtree $u$ to $e_u$, where:
    545 
    546 * The topmost chip on $e_u$ is black/white (0/1).
    547 * The length of the topmost maximal monochromatic contiguous segment on $e_u$ is $i$.
    548 
    549 When calculating $f_{u,0/1,i}$ for all $i$, we first merge the DP states of all the subtrees of node $u$, and then merge the original chips on $e_u$ into the resulting DP states.
    550 
    551 **Subtree merging**: Assume we merge two subtrees $v$ and $w$. Let $S$ and $T$ denote the number of chips on $e_v$ and $e_w$ respectively, and let $g_{0/1,i}$ be a temporary DP array initialized to all zeros.
    552 
    553 Let's consider two cases.
    554 
    555 #### **Case 1: Different colors at tops of $e_v$ and $e_w$**
    556 
    557 Suppose the top chip comes from $e_v$ after merging. Then the maximal monochromatic segment length from $e_w$ becomes irrelevant, and therefore let $h_c=\sum_{i=1}^T f_{w,c,i}$. If the top chip of $e_w$ would split the top segment of $e_v$, enumerate split positions. The split position should be strictly inside the top segment of $e_v$.
    558 
    559 $g_{c,i}\leftarrow g_{c,i} + \dbinom{S-i+T-1}{T-1} h_{1-c} \sum_{k=i+1}^S f_{v,c,k}\ (1\le i\le S)$
    560 
    561 Otherwise, the position of the top chip of $e_w$ becomes irrelevant.
    562 
    563 $g_{c,i}\leftarrow g_{c,i} + \dbinom{S-i+T}{T} h_{1-c} f_{v,c,i}$
    564 
    565 ![ ](/predownloaded/40/16/4016d5ba299b87d5130ca1161f6b2a7ddb68e991.png)
    566 
    567 With suffix sum optimization, this achieves $\mathcal{O}(m^2)$ time complexity.
    568 
    569 #### **Case 2: Same color at tops**
    570 
    571 If there are only chips of this color on both edges:
    572 
    573 $g_{c,S+T}\leftarrow g_{c,S+T} + \dbinom{S+T}{T} f_{v,c,S} f_{w,c,T}$
    574 
    575 Otherwise, assume the topmost different-colored chip is from subtree $w$ after merging. Enumerate insertion positions where this chip splits the top segment of the other (not necessarily strictly inside the segment).
    576 
    577 $g_{c,i+j}\leftarrow g_{c,i+j} + \dbinom{i+j}{j} \dbinom{S-i+T-j-1}{T-j-1} f_{w,c,j} \sum_{k=i}^S f_{v,c,k}\ (0\le i\le S,\ 1\le j \lt T)$
    578 
    579 (Similar transition equation for $v$.)
    580 
    581 ![ ](/predownloaded/ba/a7/baa7bacb9c7ebae9c301f8579636327ff2e61990.png)
    582 
    583 With suffix sum optimization, this forms a tree knapsack DP with $\mathcal{O}(m^2)$ time complexity.
    584 
    585 ---
    586 
    587 After computing $g_{0/1,i}$, we can treat $g$ as the DP states of a subtree, and continue to perform the process above.
    588 
    589 **Merging original chips on $e_u$ into the results**: We first account for internal permutations of original monochromatic segments. After that, if the bottom chip on $e_u$ shares color with merged subtrees' top chip (with segment lengths $x$ and $y$), multiply the DP state by $\dbinom{x+y}{x}$.
    590 
    591 Assuming $n$ and $m$ are of the same order, the overall time complexity is $\mathcal{O}(m^2)$.
    592 
    593 **Code**
    594 
    595 ```
    596 #include <bits/stdc++.h>
    597 #define eb emplace_back
    598 using namespace std;
    599 typedef long long ll;
    600 const int p=998244353;
    601 int T,n,m,fa[5005],col[5005],d[5005],stk[5005],top,ct[5005][2];
    602 int C[5005][5005],fac[5005],siz[5005],f[5005][2][5005],g[2][5005],ans;
    603 vector<int> to[5005],vec[5005];
    604 inline void diff(int u,int v){
    605 	int S=siz[u],T=siz[v];
    606 	for(int x=0,A,B;x<2;++x){
    607 		A=B=0;
    608 		for(int j=1;j<=T;++j)B=(B+f[v][x^1][j])%p;
    609 		for(int i=S;i>=1;--i){
    610 			g[x][i]=(g[x][i]+((ll)A*C[S+T-i-1][T-1]+(ll)f[u][x][i]*C[S+T-i][T])%p*B)%p;
    611 			A=(A+f[u][x][i])%p;
    612 		}
    613 	}
    614 }
    615 inline void same1(int u,int v){
    616 	int S=siz[u],T=siz[v];
    617 	for(int x=0,A,B;x<2;++x){
    618 		for(int i=1;i<S;++i){
    619 			if(!(A=f[u][x][i]))continue;
    620 			B=0;
    621 			for(int j=T;j>=0;--j){
    622 				B=(B+f[v][x][j])%p;
    623 				g[x][i+j]=(g[x][i+j]+(ll)A*B%p*C[i+j][j]%p*C[S-i-1+T-j][T-j])%p;
    624 			}
    625 		}
    626 	}
    627 }
    628 inline void same(int u,int v){
    629 	same1(u,v),same1(v,u);
    630 	int S=siz[u],T=siz[v];
    631 	for(int x=0;x<2;++x)
    632 		g[x][S+T]=(g[x][S+T]+(ll)f[u][x][S]*f[v][x][T]%p*C[S+T][T])%p;
    633 }
    634 inline void merge(int u,int v){
    635 	for(int i=1;i<=siz[u]+siz[v];++i)g[0][i]=g[1][i]=0;
    636 	diff(u,v),diff(v,u),same(u,v);
    637 	siz[u]+=siz[v];
    638 	for(int i=1;i<=siz[u];++i)
    639 		f[u][0][i]=g[0][i],f[u][1][i]=g[1][i];
    640 }
    641 void dfs(int u){
    642 	siz[u]=0;
    643 	for(auto v:to[u]){
    644 		dfs(v);
    645 		if(!siz[v])continue;
    646 		if(siz[u])merge(u,v);
    647 		else{
    648 			for(int i=1;i<=siz[v];++i)
    649 				f[u][0][i]=f[v][0][i],f[u][1][i]=f[v][1][i];
    650 			siz[u]=siz[v];
    651 		}
    652 	}
    653 	if(vec[u].empty())return;
    654 	int prd=1,L=vec[u].size(),c=vec[u][0],fir=0,lst=0,res=0;
    655 	for(int i=0,j=0;i<L;i=j){
    656 		while(j<L && vec[u][i]==vec[u][j])++j;
    657 		if(i==0)fir=j-i;
    658 		if(j==L)lst=j-i;
    659 		prd=(ll)prd*fac[j-i]%p;
    660 	}
    661 	for(int i=siz[u]+1;i<=siz[u]+L;++i)f[u][0][i]=f[u][1][i]=0;
    662 	if(!siz[u])f[u][vec[u][L-1]][lst]=prd;
    663 	else if(fir==L){
    664 		for(int i=siz[u];i>=1;--i){
    665 			f[u][c][i+L]=(ll)f[u][c][i]*C[i+L][i]%p*fac[L]%p;
    666 			res=(res+f[u][c^1][i])%p;
    667 			f[u][c^1][i]=0;
    668 		}
    669 		for(int i=1;i<L;++i)f[u][c][i]=0;
    670 		f[u][c][L]=(ll)res*fac[L]%p;
    671 	}
    672 	else{
    673 		for(int i=1;i<=siz[u];++i){
    674 			res=(res+(ll)f[u][c][i]*C[i+fir][i]+f[u][c^1][i])%p;
    675 			f[u][0][i]=f[u][1][i]=0;
    676 		}
    677 		f[u][vec[u][L-1]][lst]=(ll)res*prd%p;
    678 	}
    679 	siz[u]+=L;
    680 }
    681 int main(){
    682 	scanf("%d",&T);
    683 	while(T--){
    684 		scanf("%d%d",&n,&m);
    685 		for(int i=0;i<=n;++i){
    686 			to[i].clear(),vec[i].clear();
    687 			ct[i][0]=ct[i][1]=0;
    688 		}
    689 		for(int i=1;i<=n;++i)
    690 			scanf("%d",fa+i),to[fa[i]].eb(i);
    691 		for(int i=1;i<=m;++i)scanf("%d",col+i);
    692 		for(int i=1;i<=m;++i)scanf("%d",d+i);
    693 		for(int i=m,u;i>=1;--i){
    694 			top=0,u=d[i];
    695 			while(u)stk[++top]=u,u=fa[u];
    696 			for(int j=top;j>=1;--j){
    697 				if(j>1 && !ct[stk[j]][col[i]^1])continue;
    698 				vec[stk[j]].eb(col[i]),++ct[stk[j]][col[i]];
    699 				break;
    700 			}
    701 		}
    702 		C[0][0]=fac[0]=1;
    703 		for(int i=1;i<=m;++i){
    704 			for(int j=1;j<=i;++j)
    705 				C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
    706 			C[i][0]=1;
    707 			fac[i]=(ll)fac[i-1]*i%p;
    708 		}
    709 		dfs(1),ans=0;
    710 		for(int i=1;i<=m;++i)
    711 			ans=((ll)ans+f[1][0][i]+f[1][1][i])%p;
    712 		printf("%d\n",ans);
    713 	}
    714 	return 0;
    715 }
    716 ```
    717 
    718 [2081F - Hot Matrix](/contest/2081/problem/F "Codeforces Round 1010 (Div. 1, Unrated)")   
    719  Idea: [18Michael](/profile/18Michael "Grandmaster 18Michael")
    720 
    721 **Solution**
    722 
    723 First, it is not difficult to observe that when $ n $ is odd, a solution exists if and only if $ n = 1 $.
    724 
    725 When $ n $ is even, a solution always exists.
    726 
    727 Consider the following construction:
    728 
    729 Let $ n = 2m $. Use $(x, y)$ to denote the cell in the $ x $-th row and $ y $-th column of the matrix, and assume the top-left corner of the matrix is $(1, 1)$, while the bottom-right corner is $(n, n)$.
    730 
    731 For $(a, b)$ and $(c, d)$, let $ k_1 = c - a $ and $ k_2 = d - b $. When $ |k_1| = |k_2| $, denote $(a, b) \sim (c, d)$ as:
    732 
    733 * $(a, b), (a+1, b+1), \dots, (a+k_1, b+k_2)$ if $ k_1, k_2 \geq 0 $.
    734 * $(a, b), (a+1, b-1), \dots, (a+k_1, b+k_2)$ if $ k_1 \geq 0, k_2 \leq 0 $.
    735 * $(a, b), (a-1, b+1), \dots, (a+k_1, b+k_2)$ if $ k_1 \leq 0, k_2 \geq 0 $.
    736 * $(a, b), (a-1, b-1), \dots, (a+k_1, b+k_2)$ if $ k_1, k_2 \leq 0 $.
    737 
    738 For any $ 1 \leq i \leq m $, we alternately fill the numbers $ 2i-1 $ and $ 2i-2 $ in the cells along the paths $(1, 2i) \sim (n-2i+1, n)$, $(n-2i+2, n) \sim (n, n-2i+2)$, $(n, n-2i+1) \sim (2i, 1)$, and $(2i-1, 1) \sim (1, 2i-1)$.
    739 
    740 An illustration for $ n = 10 $:
    741 
    742 ![ ](/predownloaded/58/4b/584b1dbb1044b5beb3457cc5bdfda8634e2c9f84.png)
    743 
    744 Next, we prove that this construction satisfies all the requirements of the problem:
    745 
    746 * Each row and column of $ A $ is a permutation of $ 0 \sim n-1 $.
    747 
    748 **Proof**
    749 
    750 For each $ 1 \leq i \leq m $, color the cells containing the numbers $ 2i-1 $ and $ 2i-2 $ black and white alternately along the paths described above. It can be shown that each row and column contains exactly one black and one white cell, ensuring that $ 2i-1 $ and $ 2i-2 $ appear exactly once in each row and column. Thus, each row and column is a permutation of $ 0 \sim n-1 $.
    751 
    752 * $ a_{i,j} + a_{i,n-j+1} = n-1 $ and $ a_{i,j} + a_{n-i+1,j} = n-1 $.
    753 
    754 **Proof**
    755 
    756 From the filling process, the cells containing $2i-1$ and $2i-2$ and the cells containing $n-2i+1$ and $n-2i$ are symmetric with respect to the midline between the $m$-th and $(m+1)$-th rows, as well as the midline between the $m$-th and $(m+1)$-th columns. This symmetry further ensures that $ 2i-1 $ and $ n-2i $ are symmetric, as are $ 2i-2 $ and $ n-2i+1 $. Therefore, both $ a_{i,j} + a_{i,n-j+1} = n-1 $ and $ a_{i,j} + a_{n-i+1,j} = n-1 $ are satisfied.
    757 
    758 * All ordered pairs $ \langle a_{i,j}, a_{i,j+1} \rangle $ (for $ 1 \leq i \leq n, 1 \leq j \lt n $) are distinct, and all ordered pairs $ \langle a_{i,j}, a_{i+1,j} \rangle $ (for $ 1 \leq i \lt n, 1 \leq j \leq n $) are distinct.
    759 
    760 **Proof**
    761 
    762 For each $ 1 \leq i \leq m $, divide the cells containing $ 2i-1 $ and $ 2i-2 $ into four categories:
    763 
    764 * First category: $(1, 2i) \sim (n-2i+1, n)$
    765 * Second category: $(n-2i+2, n) \sim (n, n-2i+2)$
    766 * Third category: $(n, n-2i+1) \sim (2i, 1)$
    767 * Fourth category: $(2i-1, 1) \sim (1, 2i-1)$
    768 
    769 For any $ 1 \leq i \lt j \leq m $:
    770 
    771 * The first and third category cells of $ 2i-1, 2i-2 $ do not neighbor the first and third category cells of $ 2j-1, 2j-2 $ (since the sum of their coordinates is odd).
    772 * The second and fourth category cells of $ 2i-1, 2i-2 $ do not neighbor the second and fourth category cells of $ 2j-1, 2j-2 $ (since the sum of their coordinates is even).
    773 * The second and fourth category cells of $ 2i-1, 2i-2 $ do not have row-wise neighbors with the first and third category cells of $ 2j-1, 2j-2 $, and the first and third category cells of $ 2i-1, 2i-2 $ have exactly $2$ pairs of row-wise neighbors with the second and fourth category cells of $ 2j-1, 2j-2 $ (this can be visualized and proven through diagrams).
    774 
    775 Specifically:
    776 
    777 * The first category cells of $ 2i-1, 2i-2 $ and the second category cells of $ 2j-1, 2j-2 $ have exactly 2 pairs of row-wise neighbors:
    778 
    779   + $ a_{n-i-j+1,n+i-j} = 2i-2 + ((i+j+1) \bmod 2), a_{n-i-j+1,n+i-j+1} = 2j-2 + ((i+j+1) \bmod 2) $
    780   + $ a_{n-i-j+2,n+i-j+1} = 2i-2 + ((i+j) \bmod 2), a_{n-i-j+2,n+i-j} = 2j-2 + ((i+j) \bmod 2) $
    781 * The first category cells of $ 2i-1, 2i-2 $ and the fourth category cells of $ 2j-1, 2j-2 $ have exactly 2 pairs of row-wise neighbors:
    782 
    783   + $ a_{j-i,i+j-1} = 2i-2 + ((i+j) \bmod 2), a_{j-i,i+j} = 2j-2 + ((i+j+1) \bmod 2) $
    784   + $ a_{j-i+1,i+j} = 2i-2 + ((i+j+1) \bmod 2), a_{j-i+1,i+j-1} = 2j-2 + ((i+j) \bmod 2) $
    785 * The third category cells of $ 2i-1, 2i-2 $ and the second category cells of $ 2j-1, 2j-2 $ have exactly 2 pairs of row-wise neighbors:
    786 
    787   + $ a_{n+i-j+1,n-i-j+2} = 2i-2 + ((i+j) \bmod 2), a_{n+i-j+1,n-i-j+1} = 2j-2 + ((i+j+1) \bmod 2) $
    788   + $ a_{n+i-j,n-i-j+1} = 2i-2 + ((i+j+1) \bmod 2), a_{n+i-j,n-i-j+2} = 2j-2 + ((i+j) \bmod 2) $
    789 * The third category cells of $ 2i-1, 2i-2 $ and the fourth category cells of $ 2j-1, 2j-2 $ have exactly 2 pairs of row-wise neighbors:
    790 
    791   + $ a_{i+j,j-i+1} = 2i-2 + ((i+j+1) \bmod 2), a_{i+j,j-i} = 2j-2 + ((i+j+1) \bmod 2) $
    792   + $ a_{i+j-1,j-i} = 2i-2 + ((i+j) \bmod 2), a_{i+j-1,j-i+1} = 2j-2 + ((i+j) \bmod 2) $
    793 
    794 From the above analysis and by enumerating the parity of $i+j$, it is clear that all ordered pairs $ \langle a_{i,j}, a_{i,j+1} \rangle $ (for $ 1 \leq i \leq n, 1 \leq j \lt n $) are distinct, and all ordered pairs $ \langle a_{i,j}, a_{i+1,j} \rangle $ (for $ 1 \leq i \lt n, 1 \leq j \leq n $) are distinct.
    795 
    796 In conclusion, we have provided a construction for even $ n $ and proven that it satisfies all the problem's requirements.
    797 
    798 The time complexity is $O(\sum n^2)$.
    799 
    800 **Code**
    801 
    802 ```
    803 #include<bits/stdc++.h>
    804 using namespace std;
    805 int Test_num,n;
    806 int a[3002][3002];
    807 void solve()
    808 {
    809 	scanf("%d",&n);
    810 	if(n>=3 && (n&1))return (void)(puts("NO"));
    811 	puts("YES");
    812 	if(n==1)return (void)(puts("0"));
    813 	for(int i=0;i<n;i+=2)
    814 	{
    815 		for(int j=1;j<=i+1;++j)a[j][i+2-j]=i+((j&1)^1);
    816 		for(int j=i+2;j<=n;++j)a[j][j-i-1]=i+((j&1)^1);
    817 		for(int j=1;j<=n-i-1;++j)a[j][i+1+j]=i+(j&1);
    818 		for(int j=n-i;j<=n;++j)a[j][2*n-i-j]=i+(j&1);
    819 	}
    820 	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)printf("%d%c",a[i][j],j==n? '\n':' ');
    821 }
    822 int main()
    823 {
    824 	for(scanf("%d",&Test_num);Test_num--;)solve();
    825 	return 0;
    826 }
    827 ```
    828 
    829 [2081G1 - Hard Formula](/contest/2081/problem/G1 "Codeforces Round 1010 (Div. 1, Unrated)")   
    830  Idea: [Prean](/profile/Prean "Expert Prean")
    831 
    832 **Hint 1**
    833 
    834 If $g'(np)\neq g'(n)$ , then $p\le n$ unless $n=2,p=3$ or $n=1,p=2$ .
    835 
    836 **Hint 2**
    837 
    838 Think about the method of $\min 25$ sieve.
    839 
    840 **Solution**
    841 
    842 We define $\displaystyle g(n)=\frac n{\varphi(n)}=\prod_{p|n}\frac p{p-1},g'(n)=\lfloor g(n)\rfloor$.
    843 
    844 It's easy to see that $res=\frac{N(N+1)}2-\sum_{i=1}^Ng'(i)\varphi(i)$.
    845 
    846 Let's consider how to calculate $\sum_{i=1}^Ng'(i)\varphi(i)$.
    847 
    848 $\texttt{Key observation 1}$:if $g'(np)\neq g'(n)$, then $p\le n$ unless $n=2,p=3$ or $n=1,p=2$.
    849 
    850 **Proof**
    851 
    852 $ \begin{aligned} &\because g(n)\cdot\frac p{p-1}\ge g'(np)\ge g'(n)+1\\ &\therefore p\le\frac{g'(n)+1}{g'(n)+1-g(n)}\\ &\therefore p\le\dfrac{\left\lfloor\dfrac n{\varphi(n)}\right\rfloor\varphi(n)+\varphi(n)}{\left\lfloor\dfrac n{\varphi(n)}\right\rfloor\varphi(n)+\varphi(n)-n}\\ &\texttt{let}\ x=\left\lfloor\dfrac n{\varphi(n)}\right\rfloor\varphi(n)+\varphi(n)-n\ge 1\\ &\therefore p\le\dfrac{x+n}x\le n+1\\ \end{aligned} $
    853 
    854 if $p=n+1$, then $\dfrac{x+n}x=n+1\implies x=1\implies \left(1+\left\lfloor \dfrac n{\phi(n)}\right\rfloor\right)\varphi(n) = n+1 \implies \varphi(n)\mid n+1$.
    855 
    856 if $n\gt 2$ then $\varphi(n)\ge 2$, but $\varphi(n)\mid n+1=p$, which is contradict the fact that $p$ is a prime number.
    857 
    858 The case of $n\le 2$ is easy to check.
    859 
    860 Therefore, all the prime factors $p$ that $\gt \sqrt N$ wouldn't change the number of $g'(n)$.
    861 
    862 Use a linear sieve to find all the prime numbers $\le \sqrt N$, following the approach for handling composite numbers in the min25 sieve:
    863 
    864 Let's define:
    865 
    866 $s(n,k)=\varphi(n)\sum_{k\leq p\leq\lfloor\frac{N}{n}\rfloor}g'(np)\times\varphi(p)$ $S(n,k)=s(n,k)+\sum_{k\leq p\leq\sqrt N\And p^e\leq\lfloor\frac{N}{n}\rfloor}S(np^e,p)+[e\neq 1]g'(np^e)\times\varphi(np^e)$
    867 
    868 When $p\leq\frac{n+(\varphi(n)-n\mod\varphi(n))}{\varphi(n)-n\mod\varphi(n)}$, there is $g'(np)=g'(n)+1$, otherwise $g'(np)=g'(n)$.
    869 
    870 Pre-calculate the prefix of $\varphi(p)$ among prime numbers, we can calculate $s(n,k)$ like this:
    871 
    872 $s(n,k)=\varphi(n)\times\left(g'(n)\sum_{k\leq p\leq\lfloor\frac{N}{n}\rfloor}\varphi(p)+\sum_{k\leq p\leq\min\left(\frac{n+(\varphi(n)-n\mod\varphi(n))}{\varphi(n)-n\mod\varphi(n)},\lfloor\frac{N}{n}\rfloor\right)}\varphi(p)\right)$
    873 
    874 The answer is $\frac{N(N+1)}{2}-1-S(1,1)$.
    875 
    876 With time complexity $\mathcal O\left(\frac{n^{0.75}}{\log n}\right)$, it could pass the test cases of $N\le 10^{11}$.
    877 
    878 **Code**
    879 
    880 ```
    881 #include<cstdio>
    882 #include<cmath>
    883 typedef unsigned long long ull;
    884 typedef unsigned uint;
    885 const uint M=1e6+5;
    886 ull N;const uint ANS[11]={0,0,0,1,1,2,2,3,3,6,8};
    887 uint B,n4,top,pri[M],F0[M],F1[M],G0[M],G1[M],SF[M],SG[M];
    888 inline ull Div(const ull&n,const ull&m){
    889 	return double(n)/m;
    890 }
    891 inline ull min(const ull&a,const ull&b){
    892 	return a>b?b:a;
    893 }
    894 inline uint DFS(const ull&n,uint k,const ull&phi){
    895     const ull&T=Div(N,n);
    896     const uint&g=int(n*1./phi),&R=min(Div((g+1)*phi,(g+1)*phi-n),min(ull(B),T));
    897 	uint ans=0;
    898 	if(k>top)ans=T<=B?0:g*phi*(SF[n]-SG[B]);
    899 	else if(pri[k]>T)ans=0;
    900 	else if(pri[k]<=R)ans=g*phi*((n<=B?SF[n]:SG[T])-SG[R])+(g+1)*phi*(SG[R]-SG[pri[k-1]]);
    901 	else ans=g*phi*((n<=B?SF[n]:SG[T])-SG[pri[k-1]]);
    902 	for(;k<=top;++k){
    903 		const uint&p=pri[k],&w=p<=R?g+1:g;if(1ull*p*p>T)break;
    904 		for(ull x=n,tp=phi*(p-1);x*p<=N;tp*=p)ans+=DFS(x*=p,k+1,tp)+w*tp;
    905 		ans-=w*phi*(p-1);
    906 	}
    907 	return ans;
    908 }
    909 signed main(){
    910 	scanf("%llu",&N);
    911 	if(N<=10)return!printf("%d",ANS[N]);B=sqrt(N);n4=sqrt(B);
    912 	for(uint i=1;i<=B;++i){
    913 		const ull&w=Div(N,i);
    914 		F0[i]=w-1;F1[i]=w*(w+1)/2-1;
    915 		G0[i]=i-1;G1[i]=i*(i+1ull)/2-1;
    916 	}
    917 	for(uint p=2;p<=n4;++p)if(G0[p]!=G0[p-1]){
    918 		const uint&lim=Div(B,p),&S0=G0[p-1],&S1=G1[p-1];pri[++top]=p;
    919 		for(uint k=1;k<=lim;++k){
    920 			F0[k]-=F0[k*p]-S0;F1[k]-=p*(F1[k*p]-S1);
    921 		}
    922 		for(uint k=lim+1;k<=B;++k){
    923 			const uint&x=Div(N,k*p);F0[k]-=G0[x]-S0;F1[k]-=p*(G1[x]-S1);
    924 		}
    925 		for(uint k=B,e=lim;e>=p;--e)for(uint x=e*p,V0=G0[e]-S0,V1=p*(G1[e]-S1);k>=x;--k){
    926 			G0[k]-=V0;G1[k]-=V1;
    927 		}
    928 	}
    929 	for(uint p=n4+1;p<=B;++p)if(G0[p]!=G0[p-1]){
    930 		const uint&lim=Div(B,p),&T=Div(N,1ll*p*p),&S0=G0[p-1],&S1=G1[p-1];pri[++top]=p;
    931 		for(uint k=1;k<=lim;++k){
    932 			F0[k]-=F0[k*p]-S0;F1[k]-=p*(F1[k*p]-S1);
    933 		}
    934 		for(uint k=lim+1;k<=T;++k){
    935 			const uint&x=Div(N,k*p);F0[k]-=G0[x]-S0;F1[k]-=p*(G1[x]-S1);
    936 		}
    937 	}
    938 	for(uint i=1;i<=B;++i)SF[i]=F1[i]-F0[i],SG[i]=G1[i]-G0[i];
    939 	printf("%u",N*(N+1)/2-1-DFS(1,1,1));
    940 }
    941 ```
    942 
    943 [2081G2 - Hard Formula (Hard Version)](/contest/2081/problem/G2 "Codeforces Round 1010 (Div. 1, Unrated)")   
    944  Idea: [Prean](/profile/Prean "Expert Prean")
    945 
    946 **Hint 1**
    947 
    948 Consider the DFS structure of $\min 25$ sieve.
    949 
    950 What kind of nodes are important?
    951 
    952 How many of nodes are important?
    953 
    954 **Hint 2**
    955 
    956 Consider using Du Sieve to get some important functions.
    957 
    958 **Solution**
    959 
    960 For further optimization, let's consider the DFS tree of $\min25$ sieve: $N$ vertices, rooted on $1$, the father of a node $d$ is $\frac{d}{\text{maxp}(d)}$ where $\text{maxp}(d)$ denotes the maximum prime factor of $d$.
    961 
    962 Consider all the positions $d$ that $g'(d)\neq g'(fa_d)$. Let's divide them into two cases:
    963 
    964 1. $d$ is a leaf, which means $d\le N\lt d\times \operatorname{maxp}(d)$.
    965 2. $d$ is not a leaf, which means $d\times \operatorname{maxp}(d)\le N$.
    966 
    967 The answer could be calculated like this:
    968 
    969 $\sum_{g'(d)\neq g'(fa_d)\text{ or }d=1}G(\frac{d}{\mathrm{maxp}(d)},\mathrm{maxp}(d))$
    970 
    971 where $G(d,p)$ denotes the sum of $\varphi$ in the subtree of node $d$, and $G(d,p)$ could be calculated like this:
    972 
    973 $G(d,p)=\varphi(d)\sum_{i=1}^{\lfloor\frac{N}{d}\rfloor}[\mathrm{minp}(i)=p]\varphi(i)$
    974 
    975 We could use DFS to search all the nodes $d$ which satisfy case 2, and we can calculate its contribution to the answer during our DFS.
    976 
    977 For a non-leaf node $u$, let's consider its child nodes $up$ which satisfy case 1.
    978 
    979 It's easy to see that $p$ is in an interval, which allows $O(1)$ calculation of the contributions of these nodes.
    980 
    981 As a result, we get the number of nodes $d$.
    982 
    983 **DFS Code**
    984 
    985 ```
    986 //pi[n] means the number of prime number <=n
    987 //Sp[k] The prefix sum of phi(p) among the first k prime numbers
    988 //g[k]=(pri[k]-1.0)/pri[k]
    989 inline ull div(ull n,ull m){
    990     return n*1./m;
    991 }
    992 inline bool check(double P,ull n,uint k){
    993     ull x(1);while(P>1&&k<=m&&x*pri[k]<=n)P*=g[k],x*=pri[k++];return P>1;
    994 }
    995 bool DFS1(ull n,uint k,ull phi){
    996     const ull T=div(N,n);const uint w=int(1.*n/phi)+1; 
    997     if(check(w*phi*1./n,T,k))return true;
    998 	//if the g' would not change in the subtree, return directly
    999     const uint R=pi[min(div(w*phi,w*phi-n),min(ull(B),T))];
   1000     //g(n)*p/(p-1)>=int(g(n))+1
   1001     for(;k<=m;++k){
   1002         const uint&p=pri[k];if(p*p>T)break;
   1003         if(k<=R)d[k].push_back(nb(n,phi)),n*p<=K&&(lim=max(lim,k));
   1004         for(ull x=n,tp=phi*(p-1);x*p<=N;tp*=p)if(DFS1(x*=p,k+1,tp))break;
   1005 		//The subtree of np^e is isomorphic to the subtree of np^(e+1) , so if we didn't find in the previous one, we do not need to dfs into the latter one
   1006 		//This will not effect the efficiency significantly since dfs is not the efficiency bottleneck
   1007     }
   1008     if(k<=R)sum+=phi*(Sp[R]-Sp[k-1]);
   1009 	//The contribution of its child nodes which is leaf
   1010     return false;
   1011 }
   1012 ```
   1013 
   1014 | $N$ | The number of non-leaf nodes satisfy $g'(d)\neq g'(fa_d)$ | Time to DFS (tested in i9-14900HX) |
   1015 | --- | --- | --- |
   1016 | $10^{10}$ | 78370 | 0.007s |
   1017 | $10^{11}$ | 285027 | 0.021s |
   1018 | $10^{12}$ | 1074403 | 0.085s |
   1019 | $10^{13}$ | 4010656 | 0.505s |
   1020 
   1021 Let's consider how to calculate $G(d,p)$. Define:
   1022 
   1023 $f_k(x)=\sum_{i=1}^n [\text{minp}(i)\ge k]\varphi(i)$
   1024 
   1025 where $\text{minp}(i)$ denote the minimum prime number of $i$.
   1026 
   1027 Then we can see that:
   1028 
   1029 $G(d,p)=f_p(\lfloor\frac{N}{d}\rfloor)-f_{p+1}(\lfloor\frac{N}{d}\rfloor)$
   1030 
   1031 It's easy to see that $F_0(x)=\frac{\zeta(x-1)}{\zeta(x)}$, we can use Du Sieve to get all the $f_0(\lfloor \frac Nd\rfloor)$ in $O(N^{\frac 23})$.
   1032 
   1033 According to $\texttt{Key observation 1}$, $\forall d\notin{2,6},\mathrm{maxp}(d)\leq\sqrt d$.
   1034 
   1035 Let $k=\max_{g'(d)\neq g'(fa_d)\And d\leq B}(\mathrm{maxp}(d))$, categorize these nodes $d$ again:
   1036 
   1037 * (i) $\mathrm{maxp}(d)\leq k$, Then $\mathrm{maxp}(d)\leq \sqrt B$.
   1038 * (ii) $\mathrm{maxp}(d) \gt k$, then $B\leq\mathrm{maxp^2(d)}\leq d$, $\lfloor\frac{N}{d}\rfloor \lt \frac NB$.
   1039 
   1040 For those $d$ satisfy condition (i), let's begin with $f_0$, delete the prime numbers from small to large, until $f_k$ and calculate the contributions of these $d$.
   1041 
   1042 We could use Dirichlet convolution to calculate $f_{p+1}$ from $f_p$.
   1043 
   1044 Step 1:
   1045 
   1046 $h_p(N)=f_p(N)-p\times f_p(\lfloor\frac{N}{p}\rfloor)$
   1047 
   1048 Step 2:
   1049 
   1050 $f_{p+1}(N)=\sum_{i=0}h_p(\lfloor\frac{N}{p^i}\rfloor)=h_p(N)+f_{p+1}(\lfloor\frac{N}{p}\rfloor)$
   1051 
   1052 These could solve in $O\left(\frac{\sqrt N \times \sqrt B}{\log n}\right)$.
   1053 
   1054 For those $d$ satisfy condition (ii), we calculate $G(d,p)$ in this method:
   1055 
   1056 $G(d,p)=\sum_{k=1}\varphi(dp^k)f_{p+1}(\lfloor\frac{N}{dp^k}\rfloor)$
   1057 
   1058 Because $p\geq \sqrt B$ and $d\geq B$, we only need to consider $k\le \frac{\log N}{\log B}$, which is similar to $O(1)$.
   1059 
   1060 In this part, we only need $f(x)$ for $x\le B$, so to calculate these $f$ is actually a two-dimensional partial order problem which can be solved using a BIT, time complexity $O(\frac NB\log N)$.
   1061 
   1062 Since for each $d$, we get $G(d,p)$ in $O(1)$ in case (i), and $O(\log N)$ in case (ii).
   1063 
   1064 The total time complexity is $O\left(N^{\frac 23} + \frac{\sqrt N\times \sqrt B}{\log N}+ \frac NB\log N+D\log N\right)$.
   1065 
   1066 Let $B=N^{\frac 13}\log^{\frac 43}N$, the total time complexity is $O\left(N^{\frac 23}+ \frac{N^{\frac 23}}{\log^{\frac 13}N}+D\log N\right)$.
   1067 
   1068 ### Further optimization to $n=10^{13}$
   1069 
   1070 This part is included in the offline contest.
   1071 
   1072 $\texttt{Key observation 2}$ : The number of $i$ in range $[1,n]$ that satisfy $\mathrm{minp}\geq n^{\frac{1}{4}}$ is of the order of $\frac{n}{\ln n}$.
   1073 
   1074 **Proof**
   1075 
   1076 $O\left(\sum_{x=\pi(n^{\frac{1}{4}})}^{\pi(n)}\sum_{y=\pi(n^{\frac{1}{4}})}^{\pi(\frac{n}{p_x})}\max\left(\pi(\frac{n}{p_xp_y})-\pi(n^{\frac{1}{4}}),0\right)\right)=O\left(\sum_{x=\pi(n^{\frac{1}{4}})}^{\pi(n)}\pi(\frac{n}{p_x})\sum_{y=\pi(n^{\frac{1}{4}})}^{\pi(\frac{n}{p_x})}\frac{1}{p_y}\right)$ $O\left(\sum_{n^{\frac{1}{3}}\leq p\leq n}\frac{1}{p}\right)=O(\log\log n-\log\log n^{\frac{1}{3}})=O(\log 3)$ $O\left(\sum_{x=\pi(n^{\frac{1}{4}})}^{\pi(n)}\pi(\frac{n}{p_x})\sum_{y=\pi(n^{\frac{1}{4}})}^{\pi(\frac{n}{p_x})}\frac{1}{p_y}\right)=O\left(\sum_{x=\pi(n^{\frac{1}{4}})}^{\pi(n)}\pi(\frac{n}{p_x})\right)=O(\pi(n))=O(\frac{n}{\log n})$
   1077 
   1078 Since we only need to calculate $G(\frac{d}{\mathrm{maxp}(d)},\mathrm{maxp}(d))$ where $\text{maxp}(d)\gt \sqrt B$ in case (ii).
   1079 
   1080 We actually only need to consider those $\text{minp}(i)\gt \sqrt B$, and $i\le \frac{d}{\text{maxp}(d)}\le\frac N{\sqrt B}$.
   1081 
   1082 Then if $B\gt N^{\frac 13}$, the actual size to append into the BIT is only $O(\frac{N}{B\log N})$, so the time complexity of case ii is $O(\frac NB)$.
   1083 
   1084 Then we could adjust $B$ to $N^{\frac 13}\log^{\frac 23}N$, the time complexity could reduce to $O\left(\frac {N^{\frac 23}}{\log^{\frac 23}N}+D\log N+N^{\frac 23}\right)$.
   1085 
   1086 To further optimize, let's introduce a method that could significantly reduce the time consumption of Du Sieve.
   1087 
   1088 The formula of Du Sieve is $\sum_{xy\leq N}f(x)g(y)=S_{f*g}(N)$. We can see that $\min(x,y)\leq\sqrt{N}$, Let $B=\lfloor\sqrt{N}\rfloor$, the formula could be rewritten like this:
   1089 
   1090 $\sum_{i=1}^Bf(i)S_g(\lfloor\frac{N}{i}\rfloor)+g(i)S_f(\lfloor\frac{N}{i}\rfloor)-S_f(B)S_g(B)=S_{f*g}(N)$ $S_f(N)=S_{f*g}(N)+S_f(B)S_g(B)-\sum_{i=2}^Bf(i)S_g(\lfloor\frac{N}{i}\rfloor)+g(i)S_f(\lfloor\frac{N}{i}\rfloor)-S_g(N)$
   1091 
   1092 Traditionally, we need $[6B,8B]$ times of division, but using this method need a maximum of $2B$ times of division.
   1093 
   1094 As for what we need to calculate in this problem, we can get the formula:
   1095 
   1096 $S_{\varphi}(N)=\frac{N(N-1)}{2}+S_{\varphi(B)}\times B-\sum_{i=2}^B\varphi(i)\lfloor\frac{N}{i}\rfloor+iS_{\varphi}(\lfloor\frac{N}{i}\rfloor)$
   1097 
   1098 Without using things like $\text{std::map}$, and use dynamic programming instead of DFS, we can further reduce the time consumption.
   1099 
   1100 Then consider how to optimize Du Sieve to $O\left(\frac{N^{\frac{2}{3}}}{\log N}\right)$.
   1101 
   1102 Definition: if $f$ is a multiplicative function, then we define a multiplicative function $f_x(p^k)=[p\geq x]f(p^k)$.
   1103 
   1104 We can calculate $\varphi_{N^{\frac{1}{6}}}(\lfloor\frac {N}{i} \rfloor)$ for each $i$ and then recurrence $\varphi$ from $\varphi_{N^{\frac 16}}$. Let $n6=N^{\frac{1}{6}}$, we can change the formula into:
   1105 
   1106 $S_{\varphi_{n6}}(N)=S_{id_{n6}}(N)-S_{1_{n6}}(N)+S_{\varphi_{n6}}(B)S_{1_{n6}}(B)-\sum_{i=2}^B[\mathrm{minp}(i)\geq n6]\varphi(i)S_{1_{n6}}(\lfloor\frac{N}{i}\rfloor)+S_{\varphi_{n6}}(\lfloor\frac{N}{i})$
   1107 
   1108 Where $\text{id}(x)=x$ and $1(x)=1$, which can be calculated through $\text{min25}$ Seive, but we only need to solve $p\leq n6$ instead of $p\leq\sqrt N$.
   1109 
   1110 According to $\texttt{Key observation 2}$, we know that the number of $i\le \sqrt N$ that satisfy $\mathrm{minp}(i)\geq n6$ is about $\frac{\sqrt N}{\log N}$, find them and iterate these numbers in the Du Sieve. The time complexity of this part is $O\left(\frac{N^{\frac{2}{3}}}{\log N}\right)$.
   1111 
   1112 At last we get a solution of $O\left(\frac{N^{\frac{2}{3}}}{\log N}+\frac{\sqrt{NK}}{\log N}+\frac{N}{K}\right)$.
   1113 
   1114 **Code**
   1115 
   1116 ```
   1117 #include<bitset>
   1118 #include<cstdio>
   1119 #include<vector>
   1120 #include<cmath>
   1121 #include<ctime>
   1122 using std::min;
   1123 using std::max;
   1124 typedef unsigned uint;
   1125 typedef unsigned long long ull;
   1126 namespace Sol{
   1127     const uint M=4162277+5,Pi=1001258+5,M2=500000000+5;
   1128     uint sum;ull N;
   1129     uint F[M],G[M];
   1130     uint top,Sp[Pi],pri[Pi],pi[M],phi[M2];double g[Pi];
   1131     uint n4,K,B,m,lim,BIT[M];
   1132     double st,ed;
   1133     struct nb{
   1134         ull n;uint phi;
   1135         nb(const ull&n=1,const uint&phi=1):n(n),phi(phi){}
   1136     };std::vector<nb>d[Pi];
   1137     inline ull div(const ull&n,const ull&m){
   1138         return n*1./m;
   1139     }
   1140     inline void Add(uint n,const uint&V){
   1141         while(n<=B)BIT[n]+=V,n+=n&-n;
   1142     }
   1143     inline uint Qry(uint n){
   1144         uint ans(0);while(n)ans+=BIT[n],n-=n&-n;return ans;
   1145     }
   1146     inline bool check(double P,ull n,uint k){
   1147         ull x(1);while(P>1&&k<=m&&x*pri[k]<=n)P*=g[k],x*=pri[k++];return P>1;
   1148     }
   1149     inline bool DFS1(const ull&n,uint k,const ull&phi){
   1150         const ull&T=div(N,n);const uint&w=int(n/phi)+1; 
   1151         if(check(w*phi*1./n,T,k))return true;
   1152         //g(n)*p/(p-1)>=int(g(n))+1
   1153         const uint&R=pi[min(div(w*phi,w*phi-n),min(ull(B),T))];
   1154         for(;k<=m;++k){
   1155             const uint&p=pri[k];if(p*p>T)break;
   1156             if(k<=R)d[k].push_back(nb(n,phi)),n*p<=B&&(lim=max(lim,k));
   1157             for(ull x=n,tp=phi*(p-1);x*p<=N;tp*=p)if(DFS1(x*=p,k+1,tp))break;
   1158         }
   1159         if(k<=R)sum+=phi*(Sp[R]-Sp[k-1]);
   1160         return false;
   1161     }
   1162     inline void DFS2(const uint&n,uint k,const uint&phi){
   1163         const uint&T=div(B,n);Add(n,phi);
   1164         for(;k<=m;++k){
   1165             const uint&p=pri[k],&T2=div(B,p);if(p>T)return;
   1166             for(uint x=n,tp=phi*(p-1);x<=T2;tp*=p)DFS2(x*=p,k+1,tp);
   1167         }
   1168     }
   1169     void sieve(const uint&n){
   1170         phi[1]=1;
   1171         for(uint i=2;i<=n;++i){
   1172             if(!phi[i]){
   1173             	phi[i]=i-1;if(i<=B)pri[++top]=i,g[top]=1.*(i-1)/i,Sp[top]=Sp[top-1]+phi[i],pi[i]=1;
   1174 			}
   1175             for(uint x,j=1;j<=top&&(x=i*pri[j])<=n;++j){
   1176 			    phi[x]=phi[i]*(pri[j]-1);if(div(i,pri[j])*pri[j]==i){phi[x]+=phi[i];break;}
   1177 			}
   1178             if(i<=B)pi[i]+=pi[i-1];
   1179         }
   1180     }
   1181     void Getphi(const ull&n){
   1182     	const uint&B2=div(N,K);
   1183 		for(uint i=1;i<=B;++i)G[i]=G[i-1]+phi[i];for(uint i=div(N,B);i>=1;--i)F[B]+=phi[i];
   1184 		for(uint i=B-1;i>B2;--i){
   1185 			const uint&L=div(N,i+1)+1,&R=div(N,i);F[i]=F[i+1];for(uint k=L;k<=R;++k)F[i]+=phi[k];
   1186 		}
   1187     	for(uint i=B2;i>=1;--i){
   1188     		const ull&T=div(N,i);const uint&lim=sqrt(T);F[i]=lim*G[lim]+T*(T-1)/2;
   1189     		for(uint k=2;k<=lim;++k){
   1190     			const uint&x=div(T,k);F[i]-=(i*k<=B?F[i*k]:G[x])+phi[k]*x;
   1191 			}
   1192 		}
   1193     }
   1194     uint Solve(const ull&n){
   1195     	st=clock();
   1196         N=n;B=sqrt(N);n4=sqrt(B);
   1197         sieve(K=uint(pow(N,2./3)));m=pi[B];
   1198         fprintf(stderr,"sieve(%d) done %lf\n",K,((ed=clock())-st)/1000);st=ed;
   1199         DFS1(1,1,1);
   1200         fprintf(stderr,"DFS done %lf\n",((ed=clock())-st)/1000);st=ed;
   1201         Getphi(N);sum+=F[1];
   1202         fprintf(stderr,"Getphi done %lf\n",((ed=clock())-st)/1000);st=ed;
   1203         for(uint i=1;i<=lim;++i){
   1204             const uint&p=pri[i],&T=B/p;const ull&k=div(N,p);
   1205             for(nb&x:d[i])sum+=x.phi*(x.n<=B?F[x.n]:G[div(N,x.n)]);
   1206             for(uint i=1;i<=T;++i)F[i]-=p*F[i*p];
   1207             for(uint i=T+1;i<=B;++i)F[i]-=p*G[div(k,i)];
   1208             for(uint i=B,j=div(i,p);j;--j)for(uint e=j*p,V=p*G[j];i>=e;--i)G[i]-=V;
   1209             for(uint i=p,j=1;i<=B;++j)for(uint e=min(i+p,B+1),V=G[j];i<e;++i)G[i]+=V;
   1210             for(uint i=B;i>T;--i)F[i]+=G[div(k,i)];
   1211             for(uint i=T;i>=1;--i)F[i]+=F[i*p];
   1212             for(nb&x:d[i])sum-=x.phi*(x.n<=B?F[x.n]:G[div(N,x.n)]);
   1213         }
   1214         fprintf(stderr,"case1 done %lf\n",((ed=clock())-st)/1000);st=ed;
   1215         Add(1,1);
   1216         for(uint i=m;i>lim;--i){
   1217             const uint&p=pri[i];
   1218             for(nb&x:d[i]){
   1219                 ull n=N/x.n/p,phi=x.phi*(p-1);
   1220                 while(n)sum+=phi*Qry(n),n/=p,phi*=p;
   1221             }
   1222             for(ull x=p,phi=p-1;x<=B;x*=p,phi*=p)DFS2(x,i+1,phi);
   1223         }
   1224         fprintf(stderr,"case2 done %lf\n",((ed=clock())-st)/1000);st=ed;
   1225         return n*(n+1)/2-sum;
   1226     }
   1227 }
   1228 namespace sol{
   1229 	uint top,pri[10005],pos[10005],phi[10005];
   1230 	inline uint solve(const uint&N){
   1231 		uint sum(0);phi[1]=1;
   1232 		for(uint i=2;i<=N;++i){
   1233 			if(!pos[i])pri[pos[i]=++top]=i,phi[i]=i-1;
   1234 			for(uint x,j=1;j<=pos[i]&&(x=i*pri[j])<=N;++j)phi[x]=(pos[x]=j)==pos[i]?phi[i]*pri[j]:phi[i]*(pri[j]-1);
   1235 			sum+=i%phi[i];
   1236 		}
   1237 		return sum;
   1238 	} 
   1239 }
   1240 signed main(){
   1241     ull n;scanf("%llu",&n);if(n<=10000)return printf("%u\n",sol::solve(n)),0;printf("%u\n",Sol::Solve(n));
   1242 }
   1243 ```