Wonseok Shin | BOJ 16532, ICPC Latin 2018 Looking for the Risk Factor

Contents

풀이
코드

풀이

문제를 요약하자면, 매 쿼리 $(x, y)$ 마다, 2부터 $x$까지의 수 중 소인수가 모두 $y$ 이하인 수의 개수를 세는 문제이다. 두가지 서로 다른 웰노운 문제를 잘 해결할 수 있다면 합쳐서 어렵지 않게 해결할 수 있다.

에라토스테네스의 체를 살짝 응용하면, 2부터 $M$ 까지의 주어진 수들에 대해서 가장 큰 소인수 를 전부 찾는데 $O(n \log \log n)$ 시간이 걸린다. 소인수분해 체와 거의 똑같고 한두줄만 바꾸면 된다.
이제, 가장 큰 소인수 를 모두 알았으므로, 어떤 수열이 주어졌을 때 문제는 $[2, x]$ 까지의 인덱스들 중 $a_i \leq y$ 인 수들의 개수를 세는 문제가 된다. 이는 수열과 쿼리 3 문제와 비슷한데 (시작 인덱스가 고정되어 있으므로 조금 더 쉽다), 크게 두 가지 방법으로 풀 수 있다.
- 쿼리를 정렬해서, 오프라인으로 풀 수 있다. 이렇게 풀면 세그먼트 트리나 펜윅 트리 같은 걸로, 상수도 작고 시간복잡도도 $O(n \log n)$ 을 유지할 수 있다.
- 머지 소트 트리를 쓰면 온라인으로도 풀 수 있다. 머지 소트 트리에 대해서는 언젠가 글을 쓸 수도 있는데, 대략적으로 설명하자면 머지소트를 수행하는 중간 과정 을 모두 실제로 트리의 형태로 들고있는 자료구조이다. 빌드는 merge를 쓰는지 대충 하는지 여부에 따라 정말 쉽게 코딩하고 싶으면 $O(n \log^2 n)$ 시간에 트리를 빌드해도 되고, 진짜 머지소트를 쓰면 $O(n \log n)$ 시간에 빌드해도 된다. 아래 코드는 $n \log n$ 빌드.
  - 이제, 머지 소트 트리는 $[i, j]$ 에서 $k$ 보다 작거나 같은 수의 개수 (수쿼3) 형태의 쿼리를 lower_bound, upper_bound 같은 STL 함수들로 빠르게 처리할 수 있으며, 한번 쿼리에서 이 함수들을 최대 $O(\log n)$ 번 호출하므로 매 쿼리를 $O(\log^2 n)$에 처리하는 셈이 된다.
  - 쿼리는 세그먼트 트리랑 거의 똑같은 느낌으로 쿼리한다. 한번 읽어보면 대충 어떤 느낌의 자료구조인지 알기 어렵지 않다.

아래 코드는 머지소트트리, $O(n \log n)$ 버전으로 작성되어 있다.

코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
using pii = pair<int, int>;

#define MAXN (1<<18)
struct merge_sort_tree
{
    vector <int> tree[MAXN];
    int n;
    void construct (vector <int> data)
    {
        n = 1;
        while(n < data.size()) n <<= 1;
        for (int i = 0; i<data.size(); i++)
            tree[i+n] = {data[i]};
        for (int i = data.size(); i<n; i++)
            tree[i+n] = {};
        for (int i = n-1; i>0; i--)
        {
            tree[i].resize(tree[i*2].size()+tree[i*2+1].size());
            for (int p = 0, q = 0, j = 0; j < tree[i].size(); j++)
            {
                if (p == tree[i*2].size() || (q<tree[i*2+1].size() && tree[i*2+1][q]<tree[i*2][p]))
                    tree[i][j] = tree[i*2+1][q++];
                else tree[i][j] = tree[i*2][p++];
            }
        }
    }
    int greater(int s, int e, int k, int node, int ns, int ne)
    {
        if (ne <= s || ns >= e)
            return 0;
        if(s <= ns && ne <= e)
            return tree[node].end() - upper_bound(all(tree[node]), k);
        int mid = (ns+ne)>>1;
        return greater(s,e,k,node*2,ns,mid) + greater(s,e,k,node*2+1,mid,ne);
    }
    int greater(int s, int e, int k)
    {
        return greater(s,e,k,1,0,n);
    }
};

int M = 100000;
int lpd[101010];
vector <int> v(M, 0);
int32_t main()
{
    usecppio
    for (int i = 2; i <= M; i++)
    {
        if (lpd[i]) continue;
        for (int j = i; j <= M; j += i)
            lpd[j] = i;
    }
    for (int i = 1; i <= M; i++)
        v[i-1] = lpd[i];
    merge_sort_tree t;
    t.construct(v);
    int q; cin >> q;
    while(q--)
    {
        int n, k; cin >> n >> k;
        cout << n - t.greater(0, n, k) - 1 << '\n';
    }
}