输入
输入1个数N(1 <= N <= 10^18)。
输出
输出不是2 3 5 7的倍数的数共有多少。
输入样例
10
输出样例
1
如果被计数的事物有A、B、C三类,那么,A类和B类和C类元素个数总和= A类元素个数+ B类元素个数+C类元素个数—既是A类又是B类的元素个数—既是A类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。(A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C)
可扩展到N类,奇加偶减(相交的集合的个数为奇数为加,相交的集合的个数为偶数为减)
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<map>
#define INF 1e+9
using namespace std;
typedef long long ll;
#define N 52000
int main()
{
ll n;
ll a, b, c, d, ab, ac, ad, bc, bd, cd, abc,abd, acd, bcd, abcd;
scanf("%lld", &n);
a = n / 2;
b = n / 3;
c = n / 5;
d = n / 7;
ab = n / 6;
ac = n / 10;
ad = n / 14;
bc = n / 15;
bd = n / 21;
cd = n / 35;
abc = n / 30;
abd = n / 42;
acd = n / 70;
bcd = n / 105;
abcd = n / 210;
ll ans = a+b+c+d-ab-ac-ad-bc-bd-cd+abc+abd+acd+bcd-abcd;
printf("%lld
", n - ans);
return 0;
}