この問題を解きました。ネタバレを含みます。
逆から配列をなめて、それぞれの要素に対して倍数を列挙します。
解説ですぬけさんも言っていることですが、これが直感的にはO(N2)に思える（けど違う）というのがポイントで、氏曰くこの手の計算量の問題は「よくある」そうなので覚えておきたいと思います。
実際の計算量はO(N log N)になるそうですが、正直なぜそうなるのかはわかりません。
倍数だけを列挙するので全列挙と比較して極端に少なくなるというのは不思議な話ではないので深追いせずに納得しました。
二重ループの内側で倍数を列挙する部分の実装
// 逆順に処理
for(int i=N; i>=1; i--){
int cnt = 0;
// N以下のiの倍数について処理する
for(int j=i+i; j<=N; j+=i){
if(j % i == 0){
// 条件に一致したらカウントアップ
if(b[j] == 1) cnt++;
}
}
}
提出したコード
