Hello, Codeforces! The reason why I am writing this blog is that my ACM/ICPC teammate [user:calabash_boy_love_15,2019-01-18] is learning this technique recently(he is a master in string algorithms,btw), and he wanted me to provide some useful resources on this topic. I found that although many claim that they do know this topic well, problems concerning inclusion-exclusion principle are sometimes quite tricky and not that easy to deal with. Also, after some few investigations, the so-called "Inclusion-Exclusion principle" some people claim that they know wasn't the generalized one, and has little use when solving problems. So, what I am going to pose here, is somewhat the "Generalized Inclusion-Exclusion Principle". Most of the describing text are from the graduate text book _Graduate Text in Mathematics 238, A Course in Enumeration_, and the problems are those that I encountered in real problem set, so if possible, I'll add a link to the real problem so that you can solve it by yourself. I'll start with the basic formula, one can choose to skip some of the text depending on your grasp with the topic.↵
↵
Consider a finite set $\relax X$ and three subsets $\relax A,B,C$, To obtain $\vert A\cup B\cup C\vert$, we take the sum $\vert A \vert$+ $\vert B \vert$+ $\vert C \vert$. Unless $\relax A,B,C$ are pairwise distinct, we have an overcount, since the elements of $A\cap B, A\cap C,B\cap C$ has been counted twice. So we subtract $\vert A \cap B\vert + \vert A \cap C\vert + \vert B \cap C\vert$. Now the count is correct except for the elements in $A\cap B\cap C$ which have been added three times, but also subtracted three times. The answer is therefore $$\vert A\cup B\cup C\vert=\vert A \vert+ \vert B \vert+ \vert C \vert-\vert A \cap B\vert - \vert A \cap C\vert - \vert B \cap C\vert+ \vert A\cap B\cap C \vert$$,↵
or equivalently,↵
$$\vert X\backslash (A\cup B\cup C)\vert=\vert X \vert-\vert A \vert- \vert B \vert- \vert C \vert+\vert A \cap B\vert + \vert A \cap C\vert + \vert B \cap C\vert- \vert A\cap B\cap C \vert$$↵
↵
The following formula addresses the case applied to more sets.↵
↵
**The Restricted Inclusion-Exclusion Principle.** Let $\relax A_1,A_2,...,A_n$ be subsets of $\relax X$. Then↵
$$\vert X\backslash \bigcup\limits_{i=1}^{n} A_{i} \vert = \vert X \vert -\sum\limits_{i=1}^{n} \vert A_i \vert + \sum\limits_{i<j} \vert A_i \cap A_j \vert - \dots + (-1)^{n} \vert A_1 \cap \dots \cap A_n \vert$$↵
↵
This is a formula which looks familiar to many people, I'll call it The Restricted Inclusion-Exclusion Principle, it can convert the problem of calculating the size of the union of some sets into calculating the size of the intersection of some sets. It's not hard to prove the correctness of this formula, we can just check how often an element $x\in X$ is counted in both sides. If $x\notin \bigcup\limits_{i=1}^{n} A_i$, then it's counted once on either side. Suppose $x\in \bigcup\limits_{i=1}^{n} A_i$, and more precisely, that $\relax x$ is in exactly $\relax m$ of the sets $\relax A_i$. The count on the left-hand side is $\relax 0$, and on the right hand side, we have $$1-\binom{m}{1}+\binom{m}{2}-\binom{m}{3}+\dots+(-1)^{m}\binom{m}{m}=0$$ ↵
for $\relax m\ge 1$, thus the equality holds.↵
↵
**Example 1.** Let's see an example problem [Co-prime](http://acm.hdu.edu.cn/showproblem.php?pid=4135) where this principle could be applied: Given $\relax N,L,R$, you need to compute the number of integers $\relax x$ in the interval $\relax [L,R]$ such that $\relax x$ is coprime with $\relax N$, that is, $\relax gcd(x,N)=1$. There are $\relax 1\leq T\leq 100$ testcases. Constraints: $\relax 1\leq N\leq 10^{9}$, $\relax 1\leq L\leq R\leq 10^{15}$. ↵
↵
<spoiler summary="Solution">↵
If we can compute the number of integers $\relax x$ in the interval $\relax [1,X]$ such that $\relax x$ is coprime with $\relax N$, denoted as $\relax f(X)$, then the answer is $\relax f(R)-f(L-1)$. How we're gonna compute $\relax f(X)$? Instead of counting the numbers that are coprime with $\relax N$, we can count the numbers that aren't coprime with $\relax N$, that is, sharing at least one prime factor with $\relax N$. To do this, we can first sieve all primes not exceeding $\relax O(\sqrt{N})$ and then find all prime factors $\relax p_1,p_2,\dots,p_k$ of $\relax N$. Let $\relax A_{i}$ be the set of numbers that are divisible by $\relax p_{i}$, then the answer is the $\vert \bigcup\limits_{i=1}^{n} A_{k} \vert$, which may be hard to compute directly. However, using the restricted inclusion-exclusion principle, we can convert the problem into computing the size of the intersection of sets, which is trivial. Time complexity is $O(\sqrt{N}+T\cdot 2^{k})$, with $\relax k<10$ equals to the number of distinct prime factors of $\relax N$. ↵
</spoiler>↵
↵
The standard interpretation leads to the principle of inclusion-exclusion. Suppose we are given a set $\relax X$, called the _universe_, and a set $\relax E=\{e_1,e_2,\dots,e_n\}$ of **properties** that the elements of $\relax X$ may or may not process. Here we can define the properties as we like, such as $\relax e="\leq 5"$, $e="\text{is an integer}"$, or even $e="\text{likes eating bananas}"$. Let $\relax A_i$ be the subset of elements that enjoy property $\relax e_i$(and possibly others). Then $\vert X\backslash \bigcup\limits_{i=1}^{n} A_i\vert$ is the number of elements that process **none** of the properties. Clearly, $\relax A_{i_1},A_{i_2},\dots,A_{i_t}$ is the set of elements that possess the properties $\relax e_{i_1},e_{i_2},\dots,e_{i_t}$(and maybe others). Using the notation↵
↵
$$N_{\subseteq T}:=\#\{x\in X:x\text{ possesses \textit{at least} the properties in } T\}$$↵
$$N_{= T}:=\#\{x\in X:x\text{ possesses \textit{precisely} the properties in } T\}$$↵
we arrive at the inclusion-exclusion principle.↵
↵
**Inclusion-Exclusion Principle.** Let $\relax X$ be a set, and $\relax E=\{e_1,e_2,\dots,e_n\}$ a set of properties. Then ↵
$$N_{=\varnothing}=\sum\limits_{T\subseteq E}(-1)^{\vert T \vert} N_{\supseteq T}=\sum\limits_{k=0}^{n}(-1)^{k}\sum\limits_{T:\vert T \vert=k} N_{\supseteq T}$$↵
The formula becomes even simpler when $\relax N_{\supseteq T} $ depends only on the size $\vert T\vert=k$. We can then write ↵
$\relax N_{\supseteq T}=N_{\geq k}$ for $\vert T \vert=k$, and call $\relax E$ a _homogeneous_ set of properties, and in this case $\relax N_{=T}=N_{=k}$ also depends only on the cardinality of $\relax T$. Hence for homogeneous properties, we have↵
$$N_{=\varnothing}=N_{=0}=\sum\limits_{k=0}^{n}(-1)^{k}\binom{n}{k} N_{\geq k}$$↵
↵
This is the very essence of Inclusion-Exclusion Principle . Please make sure you understand every notation before you proceed. One can figure out, by letting $e_{i}=\{i\in A_{i}\}$, we arrive at the restricted inclusion-exclusion principle.↵
↵
↵
↵
**Example 2.** This problem [Character Encoding](http://acm.hdu.edu.cn/showproblem.php?pid=6397) requires you to compute the number of solutions to the equation $\relax x_{1}+x_{2}+\dots+x_{n}=k$, satisfying that $\relax 0\leq x_{i} < m$, modulo $\relax 998244353$. Constraints: $1\leq n,m,k\leq 10^5,1\leq\sum n,\sum m,\sum k\leq 5\times 10^{6}$. Hint: the number of non-negative integer solutions of $\relax x_1+x_2+\dots+x_n=k$ is given by $\binom{n+k-1}{k}=\binom{n+k-1}{n-1}$.↵
↵
↵
<spoiler summary="Solution">↵
The only thing we need to handle is to get rid of that annoying constraint $\relax x_{i}<m$. To do that, we apply the inclusion-exclusion principle. Let $\relax e_{i}="x_{i}\geq m"$, then $N_{=\varnothing}$ is our desired answer. Clearly, this set of properties is homogeneous. Take $\relax T=\{1,2,\dots,j\}(j\leq n)$, then $\relax =N_{\subseteq T}$ is the number of solutions with $\relax x_1\geq m,x_2\geq m,\dots, x_j\geq m$. Setting $\relax y_i=x_i-m(i\leq j),y_i=x_i(i>j)$, and it's the same as the number of solutions of the system $$\relax y_1+y_2+\dots+y_n=k-jm$$, thus the answer is therefore ↵
$$N_{=\varnothing}=N_{=0}=\sum\limits_{j=0}^{n}(-1)^{j}\binom{n}{j}\binom{n+k-jm-1}{n-1}$$↵
The complexity of the solution is $\relax O(n)$, due to precomputing factorials and the modular inverses of factorials.↵
↵
↵
</spoiler>↵
↵
**Example 3.** Well, this one is a well-known problem. [K-Inversion Permutations](https://www.hackerrank.com/contests/101hack43/challenges/k-inversion-permutations/problem). The statement is neat and simple. Given $N,K$, you need to output the number of permutations of length $N$ with $K$ inversions, taken modulo $\relax 10^9+7$. Constraint: $1\leq N\leq 10^5,1\leq K\leq \min(10^5,\binom{N}{2})$.↵
↵
<spoiler summary="Solution">↵
An idea one should come up with instantly is to let $\relax dp[i][j]$ as the number of permutations of length $\relax i$ with $\relax j$ inversions. The recurrence is also trivial: $dp[i][j]=\sum\limits_{k=0}^{i-1}dp[i-1][j-k]$. This is $\relax O(NK^{2})$, and can be optimized to $\relax O(NK)$ using prefix sums, which is still not enough due to the given constraints.↵
↵
Consider the dp formula, for the $\relax i$ th element, we add a number $\relax 0\leq x\leq i-1$ to the number of inversions, so the answer is equal to the number of solutions $\relax x_{1}+x_{2}+\dots+x_{n}=k$ satisfying that $\relax 0\leq x_i\leq i-1$.↵
↵
Like the last example, we can apply the inclusion-exclusion principle. Let $\relax e_{i}="x_{i} \geq i"$, then $N_{=\varnothing}$ is our desired answer. Applying the similar method we've done solving the last example, we can notice that if the sum of elements of $\relax T$ equals to $\relax s$, then the number of solutions to the equation is $N_{\supseteq T}=\binom{N-1+(K-s)}{N-1}$. Therefore, we can group those sets together. By inclusion-exclusion principle, $$N_{=\varnothing}=\sum\limits_{s=0}^{K}\binom{N-1+(K-s)}{N-1}\cdot f(i)$$↵
↵
where $f(n)=\sum\limits_{i\geq 1}(-1)^{i}g(n,i)$↵
↵
where $g(i,j)=\text{number of ways to sum up to }i\text{ using }j \text{ distinct numbers in the range} [1,N]$.↵
↵
So the problem becomes calculating all the $\relax g(i,j)$. We can use the technique as we can computing partition numbers. Partition $\relax g(i,j)$ into two cases where there exist an $\relax 1$ in the set or not, and then we get the recurrence $\relax g(i,j)=g(i-j,j)+g(i-j,j-1)$. Another important observation is that there are at most $O(\sqrt{K})$ valid values for $\relax j$. Therefore, the problem is solved in $O(K\sqrt{K})$.↵
</spoiler>↵
↵
**Example 4.** This problem comes from [XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Gomel.](http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010412)Problem K,(Yes, created by [user:tourist,2019-01-18]:) ) which gives a integer $\relax m$, and requires one to find out the number of non-empty sets of positive integers, such that their greatest common divisor is $\relax 1$, and their least common multiple is $\relax m$, taken modulo $\relax 998244353$.Constraint: $\relax 1\leq m\leq 10^{18}$.↵
↵
<spoiler summary="Solution">↵
Clearly we need to factorize $\relax m$. One may try to use Pollard-Rho algorithm under such constraints. But there's a simpler method: one can observe here only the exponents of each prime matters, no the prime itself. So we can first try to divide it using all primes up to $\relax 10^6$, and then what remains, is a prime $\relax p$, a square of a prime $\relax p^2$, or a product of two distinct primes $pq$. We can check if it's the first case using Miller-Rabin algorithm, can iterate over $\relax [sqrt(m)-10,sqrt(m)+10]$ to check if it's the second case, and otherwise the last case.↵
↵
After factorizing, we have $\relax m=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$. We need to avoid counting the cases with $\relax GCD\neq 1$ and $\relax LCM\neq m$, thus we should apply inclusion-exclusion principle. Let $e_{i,1}="\text{GCD is divisible by }p_i"$ and $e_{i,2}="\text{LCM is not divisible by }p_{i}^{a_i}"$. Then the answer is $N_{=\varnothing}$. Directly computing this would lead to the complexity of $\relax O(4^k)$,which is too much for $\relax k=15$ in te worst case. However, noticing that two of the options of for each prime divisor lead to same computations, the complexity can be reduced to $\relax O(3^k)$.↵
</spoiler>↵
↵
I guess that's the end of this tutorial. IMO, understanding all the solutions to the example problems above is fairly enough to solve most of the problems that require the inclusion-exclusion principle(but only for the IEP part XD). This is my first time of writing an tutorial. Please feel free to ask any questions in the comments below or point out any mistakes in the blog.
↵
Consider a finite set $\relax X$ and three subsets $\relax A,B,C$, To obtain $\vert A\cup B\cup C\vert$, we take the sum $\vert A \vert$+ $\vert B \vert$+ $\vert C \vert$. Unless $\relax A,B,C$ are pairwise distinct, we have an overcount, since the elements of $A\cap B, A\cap C,B\cap C$ has been counted twice. So we subtract $\vert A \cap B\vert + \vert A \cap C\vert + \vert B \cap C\vert$. Now the count is correct except for the elements in $A\cap B\cap C$ which have been added three times, but also subtracted three times. The answer is therefore $$\vert A\cup B\cup C\vert=\vert A \vert+ \vert B \vert+ \vert C \vert-\vert A \cap B\vert - \vert A \cap C\vert - \vert B \cap C\vert+ \vert A\cap B\cap C \vert$$,↵
or equivalently,↵
$$\vert X\backslash (A\cup B\cup C)\vert=\vert X \vert-\vert A \vert- \vert B \vert- \vert C \vert+\vert A \cap B\vert + \vert A \cap C\vert + \vert B \cap C\vert- \vert A\cap B\cap C \vert$$↵
↵
The following formula addresses the case applied to more sets.↵
↵
**The Restricted Inclusion-Exclusion Principle.** Let $\relax A_1,A_2,...,A_n$ be subsets of $\relax X$. Then↵
$$\vert X\backslash \bigcup\limits_{i=1}^{n} A_{i} \vert = \vert X \vert -\sum\limits_{i=1}^{n} \vert A_i \vert + \sum\limits_{i<j} \vert A_i \cap A_j \vert - \dots + (-1)^{n} \vert A_1 \cap \dots \cap A_n \vert$$↵
↵
This is a formula which looks familiar to many people, I'll call it The Restricted Inclusion-Exclusion Principle, it can convert the problem of calculating the size of the union of some sets into calculating the size of the intersection of some sets. It's not hard to prove the correctness of this formula, we can just check how often an element $x\in X$ is counted in both sides. If $x\notin \bigcup\limits_{i=1}^{n} A_i$, then it's counted once on either side. Suppose $x\in \bigcup\limits_{i=1}^{n} A_i$, and more precisely, that $\relax x$ is in exactly $\relax m$ of the sets $\relax A_i$. The count on the left-hand side is $\relax 0$, and on the right hand side, we have $$1-\binom{m}{1}+\binom{m}{2}-\binom{m}{3}+\dots+(-1)^{m}\binom{m}{m}=0$$ ↵
for $\relax m\ge 1$, thus the equality holds.↵
↵
**Example 1.** Let's see an example problem [Co-prime](http://acm.hdu.edu.cn/showproblem.php?pid=4135) where this principle could be applied: Given $\relax N,L,R$, you need to compute the number of integers $\relax x$ in the interval $\relax [L,R]$ such that $\relax x$ is coprime with $\relax N$, that is, $\relax gcd(x,N)=1$. There are $\relax 1\leq T\leq 100$ testcases. Constraints: $\relax 1\leq N\leq 10^{9}$, $\relax 1\leq L\leq R\leq 10^{15}$. ↵
↵
<spoiler summary="Solution">↵
If we can compute the number of integers $\relax x$ in the interval $\relax [1,X]$ such that $\relax x$ is coprime with $\relax N$, denoted as $\relax f(X)$, then the answer is $\relax f(R)-f(L-1)$. How we're gonna compute $\relax f(X)$? Instead of counting the numbers that are coprime with $\relax N$, we can count the numbers that aren't coprime with $\relax N$, that is, sharing at least one prime factor with $\relax N$. To do this, we can first sieve all primes not exceeding $\relax O(\sqrt{N})$ and then find all prime factors $\relax p_1,p_2,\dots,p_k$ of $\relax N$. Let $\relax A_{i}$ be the set of numbers that are divisible by $\relax p_{i}$, then the answer is the $\vert \bigcup\limits_{i=1}^{n} A_{k} \vert$, which may be hard to compute directly. However, using the restricted inclusion-exclusion principle, we can convert the problem into computing the size of the intersection of sets, which is trivial. Time complexity is $O(\sqrt{N}+T\cdot 2^{k})$, with $\relax k<10$ equals to the number of distinct prime factors of $\relax N$. ↵
</spoiler>↵
↵
The standard interpretation leads to the principle of inclusion-exclusion. Suppose we are given a set $\relax X$, called the _universe_, and a set $\relax E=\{e_1,e_2,\dots,e_n\}$ of **properties** that the elements of $\relax X$ may or may not process. Here we can define the properties as we like, such as $\relax e="\leq 5"$, $e="\text{is an integer}"$, or even $e="\text{likes eating bananas}"$. Let $\relax A_i$ be the subset of elements that enjoy property $\relax e_i$(and possibly others). Then $\vert X\backslash \bigcup\limits_{i=1}^{n} A_i\vert$ is the number of elements that process **none** of the properties. Clearly, $\relax A_{i_1},A_{i_2},\dots,A_{i_t}$ is the set of elements that possess the properties $\relax e_{i_1},e_{i_2},\dots,e_{i_t}$(and maybe others). Using the notation↵
↵
$$N_{\subseteq T}:=\#\{x\in X:x\text{ possesses \textit{at least} the properties in } T\}$$↵
$$N_{= T}:=\#\{x\in X:x\text{ possesses \textit{precisely} the properties in } T\}$$↵
we arrive at the inclusion-exclusion principle.↵
↵
**Inclusion-Exclusion Principle.** Let $\relax X$ be a set, and $\relax E=\{e_1,e_2,\dots,e_n\}$ a set of properties. Then ↵
$$N_{=\varnothing}=\sum\limits_{T\subseteq E}(-1)^{\vert T \vert} N_{\supseteq T}=\sum\limits_{k=0}^{n}(-1)^{k}\sum\limits_{T:\vert T \vert=k} N_{\supseteq T}$$↵
The formula becomes even simpler when $\relax N_{\supseteq T} $ depends only on the size $\vert T\vert=k$. We can then write ↵
$\relax N_{\supseteq T}=N_{\geq k}$ for $\vert T \vert=k$, and call $\relax E$ a _homogeneous_ set of properties, and in this case $\relax N_{=T}=N_{=k}$ also depends only on the cardinality of $\relax T$. Hence for homogeneous properties, we have↵
$$N_{=\varnothing}=N_{=0}=\sum\limits_{k=0}^{n}(-1)^{k}\binom{n}{k} N_{\geq k}$$↵
↵
This is the very essence of Inclusion-Exclusion Principle . Please make sure you understand every notation before you proceed. One can figure out, by letting $e_{i}=\{i\in A_{i}\}$, we arrive at the restricted inclusion-exclusion principle.↵
↵
↵
↵
**Example 2.** This problem [Character Encoding](http://acm.hdu.edu.cn/showproblem.php?pid=6397) requires you to compute the number of solutions to the equation $\relax x_{1}+x_{2}+\dots+x_{n}=k$, satisfying that $\relax 0\leq x_{i} < m$, modulo $\relax 998244353$. Constraints: $1\leq n,m,k\leq 10^5,1\leq\sum n,\sum m,\sum k\leq 5\times 10^{6}$. Hint: the number of non-negative integer solutions of $\relax x_1+x_2+\dots+x_n=k$ is given by $\binom{n+k-1}{k}=\binom{n+k-1}{n-1}$.↵
↵
↵
<spoiler summary="Solution">↵
The only thing we need to handle is to get rid of that annoying constraint $\relax x_{i}<m$. To do that, we apply the inclusion-exclusion principle. Let $\relax e_{i}="x_{i}\geq m"$, then $N_{=\varnothing}$ is our desired answer. Clearly, this set of properties is homogeneous. Take $\relax T=\{1,2,\dots,j\}(j\leq n)$, then $\relax =N_{\subseteq T}$ is the number of solutions with $\relax x_1\geq m,x_2\geq m,\dots, x_j\geq m$. Setting $\relax y_i=x_i-m(i\leq j),y_i=x_i(i>j)$, and it's the same as the number of solutions of the system $$\relax y_1+y_2+\dots+y_n=k-jm$$, thus the answer is therefore ↵
$$N_{=\varnothing}=N_{=0}=\sum\limits_{j=0}^{n}(-1)^{j}\binom{n}{j}\binom{n+k-jm-1}{n-1}$$↵
The complexity of the solution is $\relax O(n)$, due to precomputing factorials and the modular inverses of factorials.↵
↵
↵
</spoiler>↵
↵
**Example 3.** Well, this one is a well-known problem. [K-Inversion Permutations](https://www.hackerrank.com/contests/101hack43/challenges/k-inversion-permutations/problem). The statement is neat and simple. Given $N,K$, you need to output the number of permutations of length $N$ with $K$ inversions, taken modulo $\relax 10^9+7$. Constraint: $1\leq N\leq 10^5,1\leq K\leq \min(10^5,\binom{N}{2})$.↵
↵
<spoiler summary="Solution">↵
An idea one should come up with instantly is to let $\relax dp[i][j]$ as the number of permutations of length $\relax i$ with $\relax j$ inversions. The recurrence is also trivial: $dp[i][j]=\sum\limits_{k=0}^{i-1}dp[i-1][j-k]$. This is $\relax O(NK^{2})$, and can be optimized to $\relax O(NK)$ using prefix sums, which is still not enough due to the given constraints.↵
↵
Consider the dp formula, for the $\relax i$ th element, we add a number $\relax 0\leq x\leq i-1$ to the number of inversions, so the answer is equal to the number of solutions $\relax x_{1}+x_{2}+\dots+x_{n}=k$ satisfying that $\relax 0\leq x_i\leq i-1$.↵
↵
Like the last example, we can apply the inclusion-exclusion principle. Let $\relax e_{i}="x_{i} \geq i"$, then $N_{=\varnothing}$ is our desired answer. Applying the similar method we've done solving the last example, we can notice that if the sum of elements of $\relax T$ equals to $\relax s$, then the number of solutions to the equation is $N_{\supseteq T}=\binom{N-1+(K-s)}{N-1}$. Therefore, we can group those sets together. By inclusion-exclusion principle, $$N_{=\varnothing}=\sum\limits_{s=0}^{K}\binom{N-1+(K-s)}{N-1}\cdot f(i)$$↵
↵
where $f(n)=\sum\limits_{i\geq 1}(-1)^{i}g(n,i)$↵
↵
where $g(i,j)=\text{number of ways to sum up to }i\text{ using }j \text{ distinct numbers in the range} [1,N]$.↵
↵
So the problem becomes calculating all the $\relax g(i,j)$. We can use the technique as we can computing partition numbers. Partition $\relax g(i,j)$ into two cases where there exist an $\relax 1$ in the set or not, and then we get the recurrence $\relax g(i,j)=g(i-j,j)+g(i-j,j-1)$. Another important observation is that there are at most $O(\sqrt{K})$ valid values for $\relax j$. Therefore, the problem is solved in $O(K\sqrt{K})$.↵
</spoiler>↵
↵
**Example 4.** This problem comes from [XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Gomel.](http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010412)Problem K,(Yes, created by [user:tourist,2019-01-18]:) ) which gives a integer $\relax m$, and requires one to find out the number of non-empty sets of positive integers, such that their greatest common divisor is $\relax 1$, and their least common multiple is $\relax m$, taken modulo $\relax 998244353$.Constraint: $\relax 1\leq m\leq 10^{18}$.↵
↵
<spoiler summary="Solution">↵
Clearly we need to factorize $\relax m$. One may try to use Pollard-Rho algorithm under such constraints. But there's a simpler method: one can observe here only the exponents of each prime matters, no the prime itself. So we can first try to divide it using all primes up to $\relax 10^6$, and then what remains, is a prime $\relax p$, a square of a prime $\relax p^2$, or a product of two distinct primes $pq$. We can check if it's the first case using Miller-Rabin algorithm, can iterate over $\relax [sqrt(m)-10,sqrt(m)+10]$ to check if it's the second case, and otherwise the last case.↵
↵
After factorizing, we have $\relax m=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$. We need to avoid counting the cases with $\relax GCD\neq 1$ and $\relax LCM\neq m$, thus we should apply inclusion-exclusion principle. Let $e_{i,1}="\text{GCD is divisible by }p_i"$ and $e_{i,2}="\text{LCM is not divisible by }p_{i}^{a_i}"$. Then the answer is $N_{=\varnothing}$. Directly computing this would lead to the complexity of $\relax O(4^k)$,which is too much for $\relax k=15$ in te worst case. However, noticing that two of the options of for each prime divisor lead to same computations, the complexity can be reduced to $\relax O(3^k)$.↵
</spoiler>↵
↵
I guess that's the end of this tutorial. IMO, understanding all the solutions to the example problems above is fairly enough to solve most of the problems that require the inclusion-exclusion principle(but only for the IEP part XD). This is my first time of writing an tutorial. Please feel free to ask any questions in the comments below or point out any mistakes in the blog.
