大水题

题目

给出一个数 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;
}