AtCoder ABC 170 反省

atcoder.jp
今更ながら

結果

A,B,C問題はACした（Bは一度WAになった）。D,E,Fはいずれも手も足も出ず。

感想

数学もアルゴリズムも知識不足を感じた。蟻本と過去問演習で知識を充実させたい。

D問題復習

問題文

省略

ACしたコード

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >>n;
  vector<int>a(n);
  vector<int>tmp(1000009,0);
  for(int i=0;i<n;i++){
    cin >>a.at(i);
  }
  for(int i:a){
    if(tmp.at(i)!=0){
      tmp.at(i)=2;
      continue;
    }
    for(int j=i;j<1000009;j+=i){
      tmp.at(j)++;
    }
  }
  int ans=0;
  for(int i:a){
    if(tmp.at(i)==1)
      ans++;
  }
  cout <<ans<<endl;
}

ポイント

有名な 以下の素数を列挙するアルゴリズム（エラトステネスの篩）と同じことをやればいい。計算量はだいたい対数的だった気がするので大丈夫。何で対数的になるのかは初等的な積分から大雑把に見積もることでわかるはず（後で調べよう）。