Hust oj 1921 三原色(改进版)（容斥原理）

Dream、Griselda 还有 Sunshine正打算装饰一下集训队的墙，为了省钱，她们决定只买三原色的染料，这样就可以花费很少的钱，得到所有的颜色了O(∩_∩)O~

最初她们把墙分成了n块，编号分别为1,2,3,……n。

Dream、Griselda、sunshine分别喜欢数字x，y，z，她们只涂编号为她们喜欢的数字的倍数的墙，例如： Griselda 喜欢数字3，所以Griselda只涂编号是3,6,9,12……那些墙；

涂完之后，问这n块墙中有多少是单色调的？

本题有多组测试数据，每组测试数据输入四个正整数x,y,z,n其中满足

(0<x,y,z<=1000;0<n<=10^9)。

1 2 3 4

6 2 4 1000

1

667 

问有多少单色的，那就是相当于总的减去混色的，混色中三种颜色混色包含两种颜色混色，所以会减多，加回来就好了，就是容斥原理

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;int a,b,c,n;
int gcd(int x,int y)
{if(x < y){int temp = x;x = y;y = temp;}while(y){int temp = x % y;x = y;y = temp;}return x;
}int lcm(int x,int y)
{return x*y/gcd(x,y);
}int main()
{while(~scanf("%d%d%d%d",&a,&b,&c,&n)){int ans1 = n / lcm(a,b);int ans2 = n / lcm(a,c);int ans3 = n / lcm(b,c);int ans4 = n / lcm(a,lcm(b,c));printf("%d\n",n-ans1-ans2-ans3+2*ans4);}return 0;
}