数论——欧拉函数的自闭
点赞 + 收藏过10开始更新
有意见欢迎评论区提出
什么是容斥原理
俗话说的好,知识服务于生活,考虑如下一个生活问题:
acwing有一群热爱coding的童鞋,已知打
c++
有80000个用户,打Java的有50000个用户,acwing总共有100000个用户,且每个人都至少会c++
和Java中的一个语言,求又打Java又打c++
的有多少人?
这个时候我们就可以画出一张图了。
我们把集合这个东西用一个圆圈了表示:
c++也是可以这么表示的。
Java同理。
那么他们放在一起会怎么样呢?会有一部分重合对吧。
然后设一下就可以了。
接着就可以算出来了!
接下来我们把这个性质扩展到三种语言。
再加上Python3。
acwing有一群热爱coding的童鞋,已知打
c++
有80000个用户,打Java的有50000个用户,还有50000个打Python3的用户,acwing总共有200000个用户,且每个人都至少会c++
和Java和python3中的一个语言,求又打Java又打c++还会Python3的大佬有多少人?
好此时我们也一样先把这个图画出来昂。
这个图啊有个特殊的名字就是韦恩图。
容斥原理的图我自认为可以分为两种:
$
容斥原理
\left\\{
\begin{aligned}
大图 \\\
小图 \\\
\end{aligned}
\right.
$
分别是什么意思呢?
大家看图中的那些字母:a,b,c,d,e,f,g。
小图指的是a,b,c,d,e,f,g就代表图中它们所在的那部分。
在小图中,求整个韦恩图中元素的和的方法是:$a+b+c+d+e+f+g$
而大图就不一样了。
大图中的a部分指的其实是:a+d+g+e,也就是那个大圆形
同理,b部分指的是:b+d+g+f
c部分指的是:c+f+e+g
而d部分也不一样,指的是d+g
e部分指的是e+g
f部分指的是f+g
g没有任何变化,指的是自己。
也就是在大图中,每一部分都指的是自己和自己所包含的小部分的和。
这种方式虽然比小图表示稍微复杂了一些,但却可以通过灵活的加减来求出各部分的面积之和。
这种题目我一般习惯使用“打√法”,下面我以求和来举一个例子:
那大家尝试着解决一下上面的那个问题8!
推广到n元容斥原理
那么想象着一幅图中有n个圆,那么是不是就能得出大图的公式了呢?
先把外围所有的加一遍,然后再把下一层的减去一遍……
那么我们来试着搞一道题吧!
题目
要把一个抽象的问题转化为一个板子题,就必须把题目中给出的虚无缥缈的东西转化为数学逻辑。
那我们就先来定义一下本题的集合:$S_n$表示被n整除的数的集合。
那求的东西应该就是那个求大图的东西了。
我们先得出结论:$S_n = n / p$下取整。
那怎么求交上的呢?
一样的,因为给定的数都是两两互质的,所以也是一样的。
然后就可以使用二进制来枚举了。
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
#define ll long long
int n, m, p[N];
int main()
{
cin >> n >> m;
for(int i = 0; i < m; i ++) cin >> p[i];
int res= 0;
for(int i = 1; i < 1 << m; i ++)
{
int t = 1, cnt = 0;
for(int j = 0; j < m; j ++)
{
if(i >> j & 1)
{
cnt ++;
if((ll)t * p[j] > n)
{
t = -1;
break;
}
t *= p[j];
}
}
if(t != -1)
{
if(cnt % 2) res += n / t;
else res -= n / t;
}
}
cout << res << endl;
return 0;
}
真不错
真不错
woc怎么点的这么快,得赶紧更新了
原来集合论里union joint译名是容斥,学到了