În diagrama din dreapta este reprezentat cazul cu trei muţimi $A$, $B$ şi $C$. Relaţia de mai sus se extinde la <tex> |A \cup B \cup C|=|A|+|B|+|C|-|A \cap B|-|B \cap C|-|C \cap A|+|A \cap B \cap C| </tex>.
Pentru cazul general, având $N$ mulţimi $A{~1~},A{~2~},A{~3~}...A{~n~}$, vom presupune că există un element $x$ din
<tex> \displaystyle \bigcup_{i=1}^{n} A_{i} </tex> comun pentru exact $k$ multimi, fie acestea $A{~i1~},A{~i2~},A{~i3~}...A{~ik~}$. Vom considera cardinalele mulţimilor doar faţă de acest număr $x$ (cu alte cuvinte, ignormăm celelalte elemente). Dacă vom face intersecţia a mai mult de $k$ mulţimi, sau a unor mulţimi cu indicele de ordine diferit de $i1,i2...ik$, această intersecţie va fi evident vidă. Numărul de intersecţii a două mulţimi din cele $k$ este $C(k,2)$, numărul de intersecţii a trei mulţimi este $C(k,3)$, etc. Astfel, avem relaţia <tex> \displaystyle \bigcup_{i=1}^{k} A_{i}=C(n,1)-C(n,2)+C(n,3)+...+(-1)^k^-^1 C(n,n)=1</tex> Rezultă relaţia de demonstrat este adevărată.
<tex> \displaystyle \bigcup_{i=1}^{n} A_{i} </tex> comun pentru exact $k$ multimi, fie acestea $A{~i1~},A{~i2~},A{~i3~}...A{~ik~}$. Vom considera cardinalele mulţimilor doar faţă de acest număr $x$ (cu alte cuvinte, ignormăm celelalte elemente). Dacă vom face intersecţia a mai mult de $k$ mulţimi, sau a unor mulţimi cu indicele de ordine diferit de $i1,i2...ik$, această intersecţie va fi evident vidă. Numărul de intersecţii a două mulţimi din cele $k$ este $C(k,2)$, numărul de intersecţii a trei mulţimi este $C(k,3)$, etc. Cum am spus ca vom urmări doar elementul $x$, avem relaţia <tex> \displaystyle \bigcup_{i=1}^{k} A_{i}=C(n,1)-C(n,2)+C(n,3)+...+(-1)^{k-1} C(n,n)=1</tex> Rezultă relaţia de demonstrat este adevărată.
Pentru o demonstratie mai riguroasă puteţi citi de pe 'wikipedia':http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle sau de pe 'cut-the-knot':http://www.cut-the-knot.org/arithmetic/combinatorics/InclusionExclusion.shtml.
h3. Aplicaţie la teoria prezentă mai sus
Răspundeţi la $M$ întrebări de tipul: „dându-se două numere naturale $A$ şi $B$, să se determine numărul de numere mai mici ca $A$ şi prime cu $B$”. Două numere naturale $(x,y)$ sunt prime între daca $cmmdc(x,y)=1$.
Răspundeţi la $M$ întrebări de tipul: „dându-se două numere naturale $A$ şi $B$, să se determine numărul de numere mai mici ca $A$ şi prime cu $B$ ”. Două numere naturale $(x,y)$ sunt prime între daca $cmmdc(x,y)=1$.
h3. Care-i legătura?
* $1 ≤ M ≤ 500$
* $1 ≤ A ≤ 10^18^$
* $1 ≤ B ≤ 10^12^$
* Pentru 70% din teste $A,B ≤ 10^9^$
* Pentru $30%$ din teste $M ≤ 100, A,B ≤ 1 000$
* Pentru $70%$ din teste $A,B ≤ 10^9^$
h2. Exemplu
