描述

题目链接

给出一个数n，求1到n中，有多少个数不是2 5 11 13的倍数。

Intput

本题有多组输入
每行一个数n，1<=n<=10^18.

Output

每行输出输出不是2 5 11 13的倍数的数共有多少。

Examples

intput
1
15
output
1
4

思路

遍历一遍感觉是很快了，时间复杂度O(n)，但还是会超时，其实这道题可以达到O(1)。

我们反过来思考，用总数减去倍数的个数，先不考虑公倍数的问题，再减去公倍数的个数。

假设有三个集合，那么
A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C

代码

#include<stdio.h>
#include<iostream>
using namespace std;
#define LL long long
int main()
{
 LL n,sum;
 while(scanf("%lld",&n)!=EOF)
 {
    sum=n/2+n/5+n/11+n/13;
    LL cnt=sum-n/10-n/22-n/26-n/55-n/65-n/143+n/110+n/130+n/286+n/715-n/1430;
    LL ans=n-cnt;
    printf("%lld\n",ans);
    }
    return 0;
}