[组合数学|容斥原理]
模板代码(以求2,3,5,7倍数为例)
要点:二进制枚举
vector<int> ans;
ans.push_back(2);
ans.push_back(3);
ans.push_back(5);
ans.push_back(7);
long long sum=0;
for(int i=1;i<(1<<ans.size());i++)
{
int cnt=0;
long long tmp=1;
for(int j=0;j<ans.size();j++)
{
if(i&(1<<j))
{
tmp=tmp*ans[j];
cnt++;
}
}
if(cnt&1) sum+=n/tmp;
else sum-=n/tmp;
}