【BZOJ-4524】伪光滑数 堆 + 贪心 （暴力） [可持久化可并堆 + DP]

4524: [Cqoi2016]伪光滑数

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 183  Solved: 82
[Submit][Status][Discuss]

Description

若一个大于R的整数J的质因数分解有F项，其最大的质因子为ak，并且满足ak^k≤N，

ak<128，我们就称整数J为N-伪光滑数。

现在给出L，求所有整数中，第E大的N-伪光滑数。

Input

只有一行，为用空格隔开的整数L和E。

2 ≤ N ≤ 10^18， 1 ≤ K ≤ 800000，保证至少有 E 个满足要求的数

Output

只有一行，为一个整数，表示答案。

Sample Input

12345 20

Sample Output

9167

HINT

Source

Solution

正解是可持久化可并堆+DP,抱歉,不会...于是采用乱搞的暴力做法..

预处理出$<128$的全部质数,那么很显然,可以对数进行拆分了.

考虑题目中所说的, 所以不妨枚举倍数,对于$prime[i]^{j}$,扔进堆中,但要维护的不只一个量

然后从队首取K次即可,对于每次取出的数,除以它的最大质因子,乘上比他最大质因子小的最大的质数,再扔回堆中

方便实现这些修改,不妨在堆中记录每个数data,最大值因子次数zs,较小一位的质数的坐标nt,最大值因子的下标mp

启发:

认真计算时间复杂度,在不会最优正解的情况下,也可以写出符合时间复杂度的暴力解

类似的题目,多从质因数上考虑.实际上质数本身量较少,符合的质因子更少,所以效率会比较高效

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<queue>

using namespace std;

struct Node

{

    long long data; int zs,nt,mp;

    bool operator < (const Node & A) const

        {return data<A.data;}

}now,tmp;

priority_queue <Node> q;

long long n,x; int k,j;

int prime[50]={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,},cnt=;

int main()

{

    scanf("%lld%d",&n,&k);

    for (int i=; i<=cnt; i++)

        for (x=j=; ; j++)

            {

                x*=(long long)prime[i]; if (x>n) break;

                tmp.data=x,tmp.zs=j,tmp.nt=i-,tmp.mp=i;

                //printf("%lld %d %d %d\n",tmp.data,tmp.zs,tmp.nt,tmp.mp);

                q.push(tmp);

            }

    while (k--)

        {

            now=q.top(); q.pop();

            if (now.zs>)

                for (int i=now.nt; i; i--)

                    {

                        tmp.data=(long long)now.data/prime[now.mp]*prime[i]; tmp.zs=now.zs-; tmp.nt=i; tmp.mp=now.mp;

                        //printf("%lld %d %d %d\n",tmp.data,tmp.zs,tmp.nt,tmp.mp);

                        q.push(tmp);

                    }

        }

    printf("%lld\n",now.data);

    return ;

}