大水题
大水题
https://ac.nowcoder.com/acm/problem/15079
题目
给出一个数 n，求 1 到 n 中，有多少个数不是 2、5、11、13 的倍数。
解题思路
根据容斥原理，先不考虑重叠的情况，把 2、5、11、13 的所有倍数的数目先计算出来，然后再把计数时重复计算的数目排斥出去。
所以，1 到 n 中，这四个数的倍数的总数为cnt = n/2 + n/5 + n/11 + n/13- n/(2*5) - n/(2*11) - n/(2*13) - n/(5*11) - n/(5*13) - n/(11*13)+ n/(2*5*11) + n/(2*5*13) + n/(2*11*13) + n/(5*11*13)- n/(2*5*11*13)。
最终结果用 n 减去这四个数的倍数的数目，即 n - cnt。
C++代码
#include<iostream>
using namespace std;
int main(){
long long n;
while(cin >> n){
long long cnt = n/2 + n/5 + n/11 + n/13;
cnt -= (n/10 + n/22 + n/26 + n/55 + n/65 + n/143);
cnt += n/110 + n/130 + n/286 + n/715;
cnt -= n/1430;
cnt = n - cnt;
cout << cnt << endl;
}
return 0;
}
