CF1734C Removing Smallest Multiples 题解

FFTotoro · 2022-10-16 12:15:15 · 题解

本题需要使用类似埃氏筛的做法。

很显然，一个数如果需要被删除，那么最小的代价 k 就是它不在集合 T 内的最小质因子。

知道这一点就很好做了，枚举 [1,n] 中的所有正整数，如果 T 中没有就可以用它消去 S 中需要删除的所有数，并且给已经删掉的数打上标记即可。

这样一直做下去，我们就可以解决问题了。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n; long long c=0; string s; cin>>n>>s;
    vector<bool> b(n);
    for(int i=1;i<=n;i++){
      if(!(s[i-1]&1)){
        if(!b[i-1])c+=i;
        for(int j=2;i*j<=n;j++){
          if(!(s[i*j-1]&1)){
            if(!b[i*j-1])c+=i,b[i*j-1]=true;
          }
          else break;
        }
      }
    }
    cout<<c<<'\n';
  }
  return 0;
}