The inclusion-exclusion theorem of number theory: the number of numbers in 1-n that cannot be divisible by m numbers (non-coprime)

I have a deep understanding: Discrete mathematics is the core of the algorithm! !

Chapter – “Counting of Set Elements”, knowledge point “Exclusion Theorem” <=> “Inclusion-Exclusion Theorem”;

This article will extend the case from the teacher’s class: “The number of numbers from 1 to 1000 that cannot be divided by 5, 6, and 8” to “From the natural numbers 1 to n that cannot be divided by m integers (non-reciprocal numbers) Prime) and “The number of numbers that are divisible by at least one of the m numbers (not relatively prime) from the natural numbers 1-n“.

Note: This article omits the proof process of the binomial theorem and directly introduces the theorem and inference; the article code uses Binary enumeration to represent each option, for example, 01001 represents the selection of the 0th and 3rd property sets. plan, then the number of corresponding 1-n satisfying the property is equal to (n / lcm(p[0],p[3])), and so on; use the euclidean division method Solve for the greatest common divisor and then least common multiple.

A. Introducing Theorem 3.2 SDoes not have properties in $P_1, P_2, \cdots, P_m$ is:
\begin{aligned} & amp; \left|\bar{A}_1 \cap \bar{A}_2 \cap \cdots \cap \bar{A }_m\right| \ = & amp; |S|-\sum_{i=1}^m\left|A_i\right| + \sum_{1 \leqslant i<j \ \leqslant m}\left|A_i \cap A_j\right|- \ & amp; \sum_{1 \leqslant i<j<k \leqslant m}\left|A_i \ cap A_j \cap A_k\right| + \cdots + (-1)^m\left|A_1 \cap A_2 \cap \cdots \cap A_m\right| \end{aligned}

B. Introducing inference The number of elements in S that have at least one property is:

\begin{aligned} & amp; \left|A_1 \cup A_2 \cup \cdots \cup A_m\right| \ = & amp; \sum_{ i=1}^m\left|A_i\right|-\sum_{1<i<j<m}\left|A_i \cap A_j\right| + \ & amp; \ \sum_{1<i<j<k<m}\left|A_1 \cap A_j \cap A_1\right|-\cdots + (--1)^{m + 1}\left| A_1 \cap A_2 \cap \cdots \cap A_m\right| \end{aligned}

Case 1: Find the number of numbers from 1 to 1000 that are not divisible by 5, 6, or 8.

Let’s assume that S is a set of integers within the natural number 1000. P_1、P_2、P_3Represents three properties (divisible by 5, 6, 8) respectively, for Sx, only the following 8 can exist (2^3) case: only has the property P_1, only has the property P_2, only has the property P_3, and also has the property P_1, P_2, / P_2、P_3 / P_1、P_3(two kinds), with/without properties at the same time P_1、P_2, P_3 (three types); respectively set < img alt="A_1" class="mathcode" src="//i2.wp.com/latex.csdn.net/eq?A_1">,A_2,A_3To satisfy P_1、P_2, P_3( less than or equal to 1000) set;

According to Theorem 3.2, the formula is as follows:

\begin{aligned} & amp; \left|\bar{A}_1 \cap \bar{A}_2 \cap \bar{A}_3\right| \ = & amp; |S|-\left(\left|A_1\right| + \left|A_2\right| + \left|A_3\right|\right) + \left(\left|A_1 \cap A_2\right| + \left|A_1 \cap A_3\right| + \right. \ & amp; \left.\left |A_2 \cap A_3\right|\right)-\left|A_1 \cap A_2 \cap A_3\right| \ = & 1000-(200 + 166 + 125) + (33 + 25 + 41)-8 \ = & amp; 600 \end{aligned}

Rule: Even-numbered terms should be subtracted, and odd-numbered terms should be added;

Note: Without stating which numbers are relatively prime, \left|A_1\capA_2\right|must be the set of numbers that are divisible by lcm(5,6) .

The C++ code is as follows:

// Author: Rongrong
// Time: 2023.10.21 09:53
#include <bits/stdc + + .h>
using namespace std;
typedef long long LL;
int p[3] = {5,6,8};
int n = 1000,res;
LL gcd(LL a,LL b) {return ((a % b == 0) ? b : gcd(b, a % b));}
LL lcm(LL a,LL b) {return ((a * b) / gcd(a,b));}
int main(){
for (int i = 1; i < (1 << 3); i + + ){
int cnt = 0, pt = 1;
for (int j = 0; j < 3; j + + ){
if (i >> j & 1){
cnt + + ;
pt = lcm(pt, p[j]);
if (pt > n)
{
pt = -1;
break;
}
}
}
res = ((pt != -1) ? ((cnt & amp; 1) ? res + n / pt : res - n / pt) : res);
}
cout << n - res << endl;
return 0;
}

Output result:

Promotion Case 1: Find 1-n(n\leq 10^{9})cannot be mintegers (p[i](p[i] \leq 10^9,i \leq m = 20)) The number of numbers that are divisible.

Theorem 3.2, solved in seconds.

The C++ code is as follows:

// Author: Rongrong
// Time: 2023.10.21 09:53
#include <bits/stdc + + .h>
using namespace std;
typedef long long LL;
const int m = 25;
int p[m];
int n,m,res;
LL gcd(LL a,LL b) {return ((a % b == 0) ? b : gcd(b, a % b));}
LL lcm(LL a,LL b) {return ((a * b) / gcd(a,b));}
int main(){
cin >> n >> m;
for (int i = 0; i < m; i + + ) cin >> p[i];
for (int i = 1; i < (1 << m); i + + ){
int cnt = 0;
LL pt = 1;
for (int j = 0; j < m; j + + ){
if (i >> j & 1){
cnt + + ;
pt = lcm(pt, p[j]);
if (pt > n)
{
pt = -1;
break;
}
}
}
res = ((pt != -1) ? ((cnt & amp; 1) ? res + n / pt : res - n / pt) : res);
}
cout << n - res << endl;
return 0;
}


//Input
1000000000 3
6000000 821123 98874522
//output
999998607

Inference Case 2: Find 1-n(n\leq 10^{9}) was included in minteger (p[i](p[i] \leq 10^9,i \ \leq m = 20)) The number of numbers that are divisible by at least one number.

According to the inference, it can be solved in seconds.

// Author: Rongrong
// Time: 2023.10.21 09:53
#include <bits/stdc + + .h>
using namespace std;
typedef long long LL;
const int m = 25;
int p[m];
int n,m,res;
LL gcd(LL a,LL b) {return ((a % b == 0) ? b : gcd(b, a % b));}
LL lcm(LL a,LL b) {return ((a * b) / gcd(a,b));}
int main(){
cin >> n >> m;
for (int i = 0; i < m; i + + ) cin >> p[i];
for (int i = 1; i < (1 << m); i + + ){
int cnt = 0;
LL pt = 1;
for (int j = 0; j < m; j + + ){
if (i >> j & 1){
cnt + + ;
pt = lcm(pt, p[j]);
if (pt > n)
{
pt = -1;
break;
}
}
}
res = ((pt != -1) ? ((cnt & amp; 1) ? res + n / pt : res - n / pt) : res);
}
cout << res << endl;
return 0;
}


//Input
124552666 5
12312345 654652 546665 879465 21356464
//output
573

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56879 people are learning the system

syntaxbug.com © 2021 All Rights Reserved.