BZOJ上的题面很乱,这里有一个题面.
题解:
正解是可持久化可并堆+DP,可惜我不会...
但暴力也可过这道题.
先在不超过N的前提下,在大根堆里加入每个质数的J次方,1<=j,
然后就可以发现,当前的堆里有着不超过N的最大值.
然后每次找到堆顶,用这个数除以一次原来的质数乘上一次比它小的质数,把新数全部加入堆中.
按照这样的方式构造出第K优解.
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<string> #include<cmath> #include<ctime> #include<algorithm> #include<map> #include<set> #include<queue> #include<iomanip> using namespace std; #define ll long long #define db double #define up(i,j,n) for(ll i=j;i<=n;i++) #define pii pair<ll,ll> #define uint unsigned ll #define FILE "dealing" ll read(){ ll x=0,f=1,ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } template<class T> bool cmax(T& a,T b){return a<b?a=b,true:false;} template<class T> bool cmin(T& a,T b){return a>b?a=b,true:false;} const ll maxn=10100,limit=128; ll n,k; struct node{ ll v; ll t,pre,p; node(ll v=0,ll t=0,ll pre=0,ll p=0):v(v),t(t),pre(pre),p(p){} }temp; bool operator<(const node& a,const node& b){return a.v<b.v;} priority_queue<node> q; bool b[maxn]; ll prime[maxn],tail=0; void getprime(){ up(i,2,128){ if(!b[i])prime[++tail]=i; for(ll j=1;j<=tail&&i*prime[j]<=128;j++){ b[i*prime[j]]=1; if(i%prime[j]==0)break; } } up(i,1,tail){ ll t=1; up(j,1,128){ if((db)t*prime[i]>n)break;//注意可能爆long long q.push(node(t*=prime[i],j,i-1,i)); }// data mi pre now } } int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); n=read(),k=read(); getprime(); while(k--){ temp=q.top();q.pop(); if(temp.t>1){ for(ll i=temp.pre;i>=1;i--){ q.push(node(temp.v/prime[temp.p]*prime[i],temp.t-1,i,temp.p)); } } } printf("%lld\n",temp.v); return 0; }
本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。