题解 P4359 【[CQOI2016]伪光滑数】

这题既然没有题解，那么小蒟蒻我就来发一篇吧 说实话第一次随机到这道题，感觉思路还是混乱的，看到那个k次就联想到高精幂，然后这时机房大佬过来看了一眼，这不就是可持久化左偏树维护极值吗 一脸黑线的我~~并不知道左偏树~~，也不知道可持久化是什么高级的东西，于是开始开心的打起了暴力 首先看一下题目条件，质数最大不能超过128，那就直接打出一张表来，方便 既然不能超过N，那么就把每个质数的各次逐个加入堆，直到上限（可能非常拗口）然后就可以得到一大群欢脱的质数，因为是要求第K大，那么应该每次都从堆中取出最大的值，换掉一个他的质因子，并且乘上一个比他小的质因子里面最大的（又是非常拗口），那么就可以保证堆里面没有重复的 证明：其实就是一个搜索的思路，每次都用第一个比他小的质数来替换他，那么就相当于搜索过程中不断往下的过程，因为只取比他小的数，并且刚开始堆里面每一个元素的质因数是唯一一定的，所以不会出现重复（好吧有点啰嗦，但是你们看懂就好） 代码 ``` //Shikita #include<bits/stdc++.h> #define ll long long using namespace std; ll k,n; int p[32]={1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127}; struct node { ll val; int id,lst,nxt; bool operator < (const node &a) const { return val<a.val; } }; priority_queue<node> q; int main() { scanf("%lld%lld",&n,&k); for(int i=1;i<=31;i++) { int j=0; ll tmp=1; for(;tmp<=n/p[i];tmp*=p[i],++j); struct node x= {tmp,i,j-1,0}; q.push(x); } while(--k) { node x=q.top();q.pop(); if(x.id) { struct node y={x.val/p[x.id]*p[x.id-1],x.id-1,1,x.lst-1}; q.push(y); } if(x.nxt) { struct node y={x.val/p[x.id+1]*p[x.id],x.id,x.lst+1,x.nxt-1}; q.push(y); } } node x=q.top(); printf("%lld",x.val); return 0; } ``` 代码很丑，多多包涵，小蒟蒻我就写到这里啦 祝大家noip2018 RP++(来自一个ZJ提高组挂掉初赛的蒟蒻的祝福)