素数テーブルをO(n)で構築する

programming

$1$ から $n$ までの数が素数であるかどうかの配列(素数テーブル)を $O(n)$ で構築する。

はじめに

まず、このような素数テーブルの構築といえばいわゆるエラトステネスのふるいが有名です。小さい方から、その倍数にバツマークを付けていくと、 $O(nloglogn)$ で構築できます。実装も素直で簡単です：

const int N = 10000001;
bool prime[N];
void build_sieve(){
    fill(prime,prime+N,true);
    prime[0] = prime[1] = false;
    for(int i=2; i<N; ++i)if(prime[i]){
        for(int j=2*i; j<N; j+=i) prime[j] = false;
    }
}

実装

次に $O(n)$ の実装を見てみます。

const int N = 10000001;
int mind[N];
vector<int> pr;

void build_sieve(){
    mind[0] = mind[1] = 1;
    for(int i=2; i<N; ++i){
        if(mind[i] == 0){
            pr.push_back(i);
            mind[i] = i;
        }
        for (int j=0; j<int(pr.size()) && pr[j]<=mind[i] && i*pr[j]<N; ++j){
            mind[i*pr[j]] = pr[j];
        }    
    }
}

説明

まず、 $pr$ は素数を小さい順に持っています。

そして、 $mind$ という配列が何を情報として持っているのか見ると、mind[x]は「 $x$ を割り切る1より大きい最小の数」を持っています(0,1は例外)。

ループ内の処理を見ていくと、if文の中は $i$ が素数であることが確定しています。すでに $i-1$ までの処理が終わっていて、この時点でmindの更新が入っていないということはmind[i] = iであることが確定するということです。

つぎにその下の $j$ のループに注目します。これは $i$ が素数であるか否かに関係なく回っています。mind[i]を超えない範囲の素数を小さい順に見て行きます。

2つの数の積なので、i*pr[j]は合成数です。ここで、 $i$ を割り切る1より大きい最小の数はmind[i]なので、mind[i*pr[j]] = pr[j]は正しいです(pr[j] <= mind[i]なので)。

これがなぜうまくいっているのかについて考えると、合成数は $n = m \cdot p$ ( $m \ge 2, p$ は素数)の形で表せます。更に、この $p$ が選べるものの中で最小であると仮定すると、mind[n] = pになります。そして、この更新のタイミングは必ず $i=m$ の時にのみ来るということです。なので、mind配列の各indexへのアクセスはちょうど1回なので、この実装が $O(n)$ であると分かります。

さいごに

おおよその問題は $O(nloglogn)$ で十分だと思います。~~むしろこれが必要になるほどTime Limitがキツい問題はちょっと...~~

参考

https://codeforces.com/blog/entry/66586 ← ここに実装が書いてあります

https://codeforces.com/contest/1154/problem/G ← 元ネタの問題です

2019-05-04

CF 631 E - Product Sum

Codeforces programming

問題

Problem - E - Codeforces

問題概要

長さ $n$ の1-indexedな配列 $a$ がある。この数列に対して一度だけ、数列のある要素を選び、その要素を数列内の好きな位置に移動するという操作をすることができる。

このとき、 $c = \sum_{i=1}^n i \cdot a_i$ の取りうる最大値を求めよ。

$2 \le n \le 200000$
$| a_i | \le 1000000$

アイデア

何も動かさなかったときの $c$ の値を $c'$ として、動かしたときの差分 $\Delta c$ について考える。以下、2つの場合について考える。

ある要素を右に動かす場合

$l$ 番目の要素を、 $r$ 番目の要素となるように動かすとする( $l \lt r$ )。このとき、操作前と操作後でindexはこのようになる。

f:id:imulan:20190503233303p:plain

よって、index $1$ から $i$ までの $a$ の和を $sum_i$ とすると、

$\Delta c = l \cdot a_{l+1} + (l+1) \cdot a_{l+2} + \ldots + (r-1) \cdot a_r + r \cdot a_l - (l \cdot a_l + (l+1) \cdot a_{l+1} + \ldots + r \cdot a_r )$