求解1-n中不是5也不是6也不是8的倍数的个数

一、解法1

　　硬推公式：得到公式为n - (n / 5 + n / 6 + n / 8 - n / 30  - n / 40 - n / 24 + n /120)

　　代码实现：

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include <string>
 6 #include 
 7 #include 
 8 #include 
 9 #include <set>
10 #include 
11 #include 
12 #include 
13 #define PII pair
14 #define rep(i,z,n) for(int i = z;i <= n; i++)
15 #define per(i,n,z) for(int i = n;i >= z; i--)
16 #define ll long long
17 #define db double
18 #define vi vector
19 #define debug(x) cerr << "!!!" << x << endl;
20 using namespace std;
21 inline ll read()
22 {
23     ll s,r;
24     r = 1;
25     s = 0;
26     char ch = getchar();
27     while(ch < '0' || ch > '9'){
28         if(ch == '-')
29             r = -1;
30         ch = getchar();
31     }
32     while(ch >= '0' && ch <= '9'){
33         s = (s << 1) + (s << 3) + (ch ^ 48);
34         ch = getchar();
35     }
36     return s * r;
37 }
38 inline void write(ll x)
39 {
40     if(x < 0) putchar('-'),x = -x;
41     if(x > 9) write(x / 10);
42     putchar(x % 10 + '0');
43 }
44 int main()
45 {
46     ll n;
47     cin >> n;
48     cout << n - (n / 5 + n / 6 + n / 8 - n / 30 - n / 40 - n / 24 + n / 120) << endl;
49     return 0;
50 }

二、借助韦恩图观察

 三个圈代表5 和 6 和 8的倍数的数

首先我们求是5的倍数就是n/5

　　然后就是6的倍数就是n/6

　　然后就是8的倍数就是n/8

　　我们会发现多加了重复的部分（彩色部分）

　　也就是5和6的中间，5和8的中间，6和8的中间

　　然后就是减去n/30（30是5和6的最小公倍数)

　　然后就是减去n/24 （24是6和8的最小公倍数)

　　然后就是减去n/40（40就是5和8的最小公倍数）

　　我们发现会多减了5 和 6 和 8中间的一部分（蓝色部分）

　　那我们就要加回来就是n/(120）（120是5和6和8的最小公倍数)

　　代码实现如上

离散数学

相关

关于离散数学到了期末这件事

标签