【LOJ】#2047. 「CQOI2016」伪光滑数

题解

可持久化可并堆

用\(f[i,j]\)表示最大的质数标号为i，然后有j个质数乘起来

用\(g[i,j]\)表示\(\sum_{k = 1}^{i}f[k,j]\)

转移是

\(f[i,j] = \sum_{k= 1}^{j} g[i - 1,j - k] * p_{i}^{k}\)

\(g[i,j] += f[i,j]\)

这就要资瓷两个集合的合并了

可是集合显然非常大，我们可以用可持久化来帮助完成这件事，就完成了

代码

#include <bits/stdc++.h>

#define enter putchar('\n')

#define space putchar(' ')

#define pii pair<int,int>

#define fi first

#define se second

#define MAXN 1000005

#define pb push_back

#define mp make_pair

#define eps 1e-8

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

        if(c == '-') f = -1;

        c = getchar();

    }

    while(c >= '0' && c <= '9') {

        res = res * 10 + c - '0';

        c = getchar();

    }

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) out(x / 10);

    putchar('0' + x % 10);

}

int64 N;

int K,prime[105],tot;

bool nonprime[205];

int64 pw[105];

struct node {

    node *lc,*rc;

    int64 mul,val;

    int dis;

}pool[17000000],*tail = pool;

struct set_node {

    int64 val;node *rt;

    set_node(){}

    set_node(int64 _v,node *r) {

        val = _v;rt = r;

    }

    friend bool operator < (const set_node &a,const set_node &b) {

        return a.val > b.val;

    }

    friend bool operator == (const set_node &a,const set_node &b) {

        return a.val == b.val && a.rt == b.rt;

    }

};

node *g[105],*f[105];

set<set_node > S;

node *Newnode(int64 v) {

    node *res = tail++;

    res->mul = 1;res->val = v;

    res->lc = res->rc = NULL;

    res->dis = 0;

    return res;

}

int getdist(node *p) {

    return p ? p->dis : -1;

}

node* addlazy(node *u,int64 val) {

    if(!u) return NULL;

    node *res = tail++;

    *res = *u;

    res->val *= val;

    res->mul *= val;

    return res;

}

void push_down(node *&u) {

    if(u->mul != 1) {

        u->lc = addlazy(u->lc,u->mul);

        u->rc = addlazy(u->rc,u->mul);

        u->mul = 1;

    }

}

node *Merge(node *A,node *B) {

    if(!A) return B;

    if(!B) return A;

    if(A->val < B->val) swap(A,B);

    push_down(A);

    node *res = tail++;

    *res = *A;

    res->rc = Merge(A->rc,B);

    if(getdist(res->rc) > getdist(res->lc)) swap(res->lc,res->rc);

    res->dis = getdist(res->rc) + 1;

    return res;

}

void Solve() {

    read(N);read(K);

    for(int i = 2 ; i <= 128 ; ++i) {

        if(!nonprime[i]) {

            prime[++tot] = i;

            for(int j = 2 ; j <= 128 / i ; ++j) {

                nonprime[i * j] = 1;

            }

        }

    }

    for(int i = 0 ; i <= 100 ; ++i) g[i] = NULL;

    g[0] = Newnode(1);

    for(int i = 1 ; i <= tot ; ++i) {

        int cnt = 0;int64 t = N;

        while(t >= prime[i]) {t /= prime[i];++cnt;}

        pw[0] = 1;

        for(int k = 1 ; k <= cnt ; ++k) pw[k] = pw[k - 1] * prime[i];

        for(int k = 1 ; k <= cnt ; ++k) {

            f[k] = NULL;

            for(int h = 1 ; h <= k ; ++h) {

                f[k] = Merge(f[k],addlazy(g[k - h],pw[h]));

            }

        }

        for(int k = 1 ; k <= cnt ; ++k) g[k] = Merge(g[k],f[k]);

    }

    node *rt = NULL;

    for(int i = 1 ; i <= 100 ; ++i) rt = Merge(rt,g[i]);

    S.insert(set_node(rt->val,rt));

    for(int i = 1 ; i < K ; ++i) {

        set_node p = *S.begin();

        S.erase(S.begin());

        push_down(p.rt);

        if(p.rt->lc) S.insert(set_node(p.rt->lc->val,p.rt->lc));

        if(p.rt->rc) S.insert(set_node(p.rt->rc->val,p.rt->rc));

        while(S.size() > K - i) S.erase(--S.end());

    }

    out((*S.begin()).val);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

巴特西

【LOJ】#2047. 「CQOI2016」伪光滑数

题解

代码

最新文章

热门文章