裏紙

ほぼ競プロ、たまに日記

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

 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 ← 元ネタの問題です

CF 631 E - Product Sum

問題

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

よって、index1から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 )

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

 = (r-l) \cdot a_l - (sum_r - sum_l)

 =  r \cdot a_l - sum_r + sum_l - l \cdot a_l

となり、これはCHTを利用し、lを減らしていきながら探索することでO(nlogn)で探索することができる(傾きには単調性がある方向で追加している)。

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

r番目の要素を、l番目の要素となるように動かすとする(l \lt r)。

これも同様に計算すると、\Delta c = l \cdot a_r - sum_{l-1} + sum_{r-1} - r \cdot a_rとなり、今度はrを基準にすることで同様に探索ができる。

実装(C++)

続きを読む