codeforces 630K - Indivisibility

时间:2023-03-09 09:57:24
codeforces 630K - Indivisibility

K. Indivisibility

题意:给一个n(1 <= n <= 10^18)的区间,问区间中有多少个数不能被2~10这些数整除;

整除只需要看素数即可,只有2,3,5,7四个素数;基本的容斥原理;数据很小直接用二进制模拟了;

int main()
{
ll n,a[] = {,,,};
scanf("%I64d",&n);
ll cnt = n;
for(int id = ;id < (<<);id++){
int num = ;
rep0(i,,)if(id &(<<i)){
num *= a[i];
}
int t = ;
if(__builtin_popcount(id) & ) t = -;
cnt += 1LL*t*(n/num);
}
cout<<cnt;
return ;
}