本文共 1273 字，大约阅读时间需要 4 分钟。
Problem Description
V_Dragon有n栈电灯泡，编号为1-n，每个灯泡都有一个开关。那么问题来了
1.所有灯泡初始时为不亮的
2.V_Dragon分别进行三次操作
3.每次操作他都选一个质数x，将编号为x和x的整数倍的灯泡的开关都拨动一下（如果灯为亮，那么拨动以后灯为不亮,如果灯不亮，拨动以后变为亮）
求最后亮着的灯的数量
Input
输入T表示T组测试数据（1<=T<=100）
接下来T组测试数据
每组第一行一个n表示灯泡个数（1<=n<=10^9）
第二行三个数a,b,c表示V_Dragon每次选择的数（1<=a,b,c<=10^6）（a,b,c全为质数且a,b,c两两互不相等）
不懂格式的同学可以参考以下格式：
Output
数组最后亮着的灯的个数
SampleInput
1
30 2 3 5SampleOutput
15
这个题是昨天晚上在b站上看容斥算法时给出的一道题，当时也没想明白，事后自己想了想。这其实就是三个集合容斥的简单变形。。题目最终要求的是求还有多少灯开着，但是如果按着原来的方法做，肯定是不行的。那样只是求得个数，但是和灯亮的个数是不同的。 原来的方法：a+b+c-ab-ac-bc+abc。这样的话a+b+c代表的是啊a,b,c总的要摁的灯的按钮。而ab,bc,ac代表的是这两个数的倍数，就是两次摁同一个灯。这里我们应该想一下，如果只是减一个的话，那么还是和原来一样，交接的地方还是有剩余的。。但是对一个灯操作两次，灯就关了。这样就不需要计算这一块了。所以应该减两次。再看+abc。我们将在前面已经-2*(ab+bc+ac)了，就相当于将abc这一块减了三次，但是对于abc这一块，三次操作还是亮着的。所以应该加上4*（abc）。所以最后的公式应该是a+b+c-2ab-2bc-2ac+4abc. 代码如下：#include#include #include #include #include #define ll long longusing namespace std;ll n;ll a,b,c;int main(){ int t; scanf("%d",&t); while(t--) { scanf("%lld",&n); scanf("%lld%lld%lld",&a,&b,&c); ll num1=n/a; ll num2=n/b; ll num3=n/c; ll ab=n/(a*b); ll bc=n/(b*c); ll ac=n/(a*c); ll abc=n/(a*b*c); printf("%lld\n",num1+num2+num3-2*(ab+ac+bc)+4*(abc)); }}
第一次接触容斥原理，挺难的，不太好理解，还需要努力呀。
努力加油a啊，(o)/~转载地址：http://szxvi.baihongyu.com/