题目描述
给一个数n，找出1 ~ n 范围内不被 2 ~ 10整除的数的个数
输入
一个数n
输出
1–n范围内不被2–10整除的数的个数
样例输入
12
样例输出
2
提示
数据范围：1<=n<=1018
2–10以内的素数有 2 3 5 7
根据容斥原理：结果应该等于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
其中—>6是2和3的乘积，10是2和5的乘积，14是2和7的乘积，15是3和5的乘积，21是3和7的乘积，35是5和7的乘积(加)
30是2，3，5的乘积，42是2 3 7的乘积，70是2 5 7的乘积，105是3 5 7 的乘积（减）
210为2 3 5 7的乘积（加）
参考代码：
#include <bits/stdc++.h> #include <algorithm> typedef long long ll; using namespace std; ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar(); if(c == '-')Nig = -1,c = getchar(); while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar(); return Nig*x;} #define read read() int main() { ll n=read; cout<<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<<endl; return 0; } /************************************************************** Problem: 3814 Language: C++ Result: 正确 Time:1 ms Memory:6788 kb ****************************************************************/
