naoya_t@hatenablog

いわゆるチラシノウラであります

〈過去問〉みんなのプロコン2018決勝 A: Uncommon

こないだのSRM734 Easyの類題。(agwたんより)

N個の数 \{a_i\} (1\le a_i \le 10^5) が与えられている。
整数Mが与えられたとき、1からMのすべての整数 q について、\{a_i\} の中で q と互いに素なものの個数を答えていくクエリ問題。
N,Mの範囲は1\le N,M \le 10^5

クエリでやりたいこと:

  • qをとりあえず素因数分解する。例えばq=120ならq=120=2^3\times3\times5。使いたいのは重複を排した集合S (2,3,5)。
  • Sそれぞれについて、\{a_i\} の中にその倍数(2の倍数・3の倍数・5の倍数)がそれぞれいくつあるかO(1)で調べたい(ので表を作っておきたい)。
  • Sから素因数を2つ選んでかけ合わせた数(2x3=6, 2x5=10, 3x5=15)それぞれについて \{a_i\} の中にその倍数(6の倍数・10の倍数・15の倍数)がそれぞれいくつあるかO(1)で調べたい[ので表を作っておきたい]。
  • Sから素因数を3つ選んでかけ合わせた数(2x3x5=30)それぞれについて \{a_i\} の中にその倍数(30の倍数)がいくつあるかO(1)で(略)。
  • Sのすべての素因数をかけ合わせた数になるまで続ける。
  • ここまで出来れば、qの素因数の少なくともどれか1つの倍数であるものが \{a_i\} にいくつあるかは包除原理で分かる。(包除原理については略。)訊かれているのは互いに素なものの個数なのでNからそれを引いて答えればよい。

クエリ前に用意しておくべきこと:

  • 10^5 までの素数
  • 素因数分解を高速に行うための smallest_prime_factor 的なテーブル。(これはエラトステネスの篩をやりながら作れる。)
  • 10^5 までの素数 p について、\{a_i\} の中にその倍数がいくつあるかをO(1)で知ることができる手段(int[]テーブル)
  • 複数の異なる素数の積 P について、\{a_i\} の中にその倍数がいくつあるかをO(1)で知ることができる手段(int[]テーブル)。これは先程のテーブルと同じ物に入れてよい。実際は \{a_i\} に出てこないようなPについては考える必要はない。

というわけで、\{a_i\} それぞれを素因数分解して得た素因数集合について、空集合以外の全ての部分集合について要素の積Pを求めて ++table[P] していく。10^5 までだと素因数の個数は重複を排すれば高々6個(平均2.664)なので、高々 2^6-1=63箇所のインクリメント(平均で6.785回)が発生する。素因数分解自体も重複を含めて高々16個(10^5 までだと65536=2^16が最多。平均3.436個)で、smallest_prime_factorをその個数回辿っていくだけの処理なので、Mまでの整数を素因数分解した際の素因数の個数が最大でRとするなら、計算量は最悪の場合でもO(N2^R)である。

クエリ処理(q=[1..M])

  • qを素因数分解して得た素因数集合について、空集合以外の全ての部分集合について要素の積Pを求めて table[P] の値を答えに足すなり引くなりしていく。(足すか引くかというのは、包除原理なので部分集合の要素数が奇数なら足して、偶数なら引いていく)

Mまでの整数を素因数分解した際の素因数の個数(重複なし)が最大でRとするなら、計算量は最悪の場合でもO(M2^R)である。

クエリ前の用意も合わせると、計算量は O((N+M)2^R) になる。
エラトステネスの篩の計算量はO(n\log\log n)だけど、n\log\log nn\cdot 2^Rってどっちが大きい?

素因数 - Wikipedia によるとnの素因数の個数(重複なし)Rは最大で \displaystyle\frac{\log n}{\log\log n-1.1714}とのこと。重複ありでも最大  \displaystyle\log_2 n
f:id:n4_t:20180526142639p:plain
グラフを描いてみたらn\log\log n(上の曲線)の方が  \displaystyle n\cdot^\frac{\log n}{\log\log n-1.1714} (下の曲線)より大きかった。

発展

準備段階と各クエリで同じパターンの処理が2回記述されていて冗長なので、λ式を使ってまとめてみる。

λ式を関数の引数にする時はstd::functionで受ける。(いつも忘れるので書いておく)。

(・・・略・・・)

int cnt[100001];

inline int _pattern(int num, function<int(int,int)> proc){
    vi f = factorize(num);
    int w = f.size();
    int P = 1 << w;
    int sum = 0;
    for (int p=1; p<P; ++p) {
        int x = 1;
        int pm = -1;
        for (int b=0,m=1; b<w; ++b,m<<=1) {
            if (p & m) {
                x *= f[b];
                pm = -pm;
            }
        }
        sum += proc(x,pm);
    }
    return sum;
}

int main() {
    mset(cnt, 0);
    sieve(1e5);

    int N,M; cin >> N >> M;

    rep(i,N) {
        int ai; cin >> ai;
        _pattern(ai, [](int x,int pm){
           return ++cnt[x]; // ここの返り値は使われないので何を返してもよい
        });
    }

    rep1(i,M){
        int ans = N - _pattern(i, [](int x,int pm){
            return cnt[x] * pm;
        });
        cout << ans << endl;
    }

    return 0;
}

λ式を使うと処理が重くなるんじゃないかと思って敬遠しがちなのだけれど、今回は変数キャプチャをしていないせいか元のやつと同じか、あるいは微妙に速いんじゃないかという結果になった。
https://yahoo-procon2018-final-open.contest.atcoder.jp/submissions/2559821
ジャッジサーバ上でも問題なく動作した。