普通的研究生。

[组合数学|容斥原理]

模板代码(以求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;
 }

评论

© 方鸢子 | Powered by LOFTER