Back to : algorithms
Contents

ํ’€์ด

๋ฌธ์ œ๋ฅผ ์š”์•ฝํ•˜์ž๋ฉด, ๋งค ์ฟผ๋ฆฌ $(x, y)$ ๋งˆ๋‹ค, 2๋ถ€ํ„ฐ $x$๊นŒ์ง€์˜ ์ˆ˜ ์ค‘ ์†Œ์ธ์ˆ˜๊ฐ€ ๋ชจ๋‘ $y$ ์ดํ•˜์ธ ์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ์„ธ๋Š” ๋ฌธ์ œ์ด๋‹ค. ๋‘๊ฐ€์ง€ ์„œ๋กœ ๋‹ค๋ฅธ ์›ฐ๋…ธ์šด ๋ฌธ์ œ๋ฅผ ์ž˜ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค๋ฉด ํ•ฉ์ณ์„œ ์–ด๋ ต์ง€ ์•Š๊ฒŒ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค.

  1. ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด๋ฅผ ์‚ด์ง ์‘์šฉํ•˜๋ฉด, 2๋ถ€ํ„ฐ $M$ ๊นŒ์ง€์˜ ์ฃผ์–ด์ง„ ์ˆ˜๋“ค์— ๋Œ€ํ•ด์„œ ๊ฐ€์žฅ ํฐ ์†Œ์ธ์ˆ˜ ๋ฅผ ์ „๋ถ€ ์ฐพ๋Š”๋ฐ $O(n \log \log n)$ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฐ๋‹ค. ์†Œ์ธ์ˆ˜๋ถ„ํ•ด ์ฒด์™€ ๊ฑฐ์˜ ๋˜‘๊ฐ™๊ณ  ํ•œ๋‘์ค„๋งŒ ๋ฐ”๊พธ๋ฉด ๋œ๋‹ค.
  2. ์ด์ œ, ๊ฐ€์žฅ ํฐ ์†Œ์ธ์ˆ˜ ๋ฅผ ๋ชจ๋‘ ์•Œ์•˜์œผ๋ฏ€๋กœ, ์–ด๋–ค ์ˆ˜์—ด์ด ์ฃผ์–ด์กŒ์„ ๋•Œ ๋ฌธ์ œ๋Š” $[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';
    }
}