基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题
收藏
关注给出一个数N，求1至N中，有多少个数不是2 3 5 7的倍数。 例如N = 10，只有1不是2 3 5 7的倍数。
Input
输入1个数N(1 <= N <= 10^18)。
Output
输出不是2 3 5 7的倍数的数共有多少。
Input示例
10
Output示例
1
容斥原理
第一次接触
举个例子
A∪B∪C∪D=|A|+|B|+|C|+|D| - |A∩B| - |B∩C| - |C∩A|- |A∩D| - |B∩D| - |C∩D|+|A∩B∩C|+|A∩B∩D| +|A∩C∩D|+|B∩C∩D| -|A∩B∩C∩D|
推导过程我们可以先看三个，比如你过程中出现的|B∪C∪D|
|B∪C∪D|=|B|+|C∪D|-|B∩(C∪D)|=|B|+|C|+|D|-|C∩D|-|[(B∩C)∪(B∩D)]|
=|B|+|C|+|D|-|C∩D|-|B∩C|-|B∩D|+|B∩C∩D|
//
关于此题 代码上已经推出了非常多的规律了
分开写会爆longlong
合在一起写就行
知道规律是非常快的
235的集合数就是5集合数/2*3
#include <iostream>
using namespace std;
int main()
{
//long long v2,v3,v5,v7;
//long is23,is25,is27,is35,is37,is57,is235,is237,is257,is357,is2357;
long long n;
cin>>n;
/*v2 = n / 2;
v3 = n / 3;
v5 = n / 5;
v7 = n / 7;
is23 = v3 / 2;
is25 = v5 / 2;
is27 = v7 / 2;
is35 = v5 / 3;
is37 = v7 / 3;
is57 = v7 / 5;
is235 = v5 / 6;
is237 = v7 / 6;
is257 = v7 / 10;
is357 = v7 / 15;
is2357 = v7 / 30;
//cout<<v2<<' '<<v3<<' '<<v5<<' '<<is23<<' '<<is35<<' '<<is25<<' '<<is235<<' '<<endl;
long long ans = v2 + v3 + v5 + v7 - is23 - is25 -is27 - is35 - is37 - is57 + is235 + is237 + is257 + is357 - is2357;
ans = n - ans;
cout<<ans<<endl;*/
long long ans;
ans = n - (n / 2 + n / 3 + n / 5 + n / 7 - n / 6 - n / 10 - n / 14 - n / 15 - n / 21 - n / 35 + n / 30 + n / 42 + n / 70 + n / 105 - n / 210);
cout<<ans<<endl;
return 0;
}