聽說這道題標(biāo)算是可持久化可并堆，但是用優(yōu)先隊(duì)列+貪心可以卡過去%%%。 首先找出所有小于128的質(zhì)數(shù)，如果某個質(zhì)數(shù)的q次方（q任取）小于n，那么這就是一個可行方案，加入優(yōu)先隊(duì)列。 接著每次取出一個方案，去掉一個質(zhì)因數(shù)，加入一個較小的質(zhì)因數(shù)，就形成了一個新的方案，加入隊(duì)列，一直取k次即可。 具體實(shí)現(xiàn)方式是用一個四元組(x,i,j,k)表示一種方案，其中x表示當(dāng)前的數(shù)；i那個最大的質(zhì)因數(shù)的次數(shù)；j表示上一次加入的質(zhì)因數(shù)，因?yàn)闉榱吮ＷC每一次方案不重復(fù)，加入的質(zhì)因數(shù)必須越來越小；k表示最大的質(zhì)因數(shù)。
#include<cmath>#include<cstdio>#include<vector>#include <queue>#include<cstring>#include<iomanip>#include<stdlib.h>#include<iostream>#include<algorithm>#define ll long long#define inf 1000000000#define mod 1000000007#define N 20000#define fo(i,a,b) for(i=a;i<=b;i++)#define fd(i,a,b) for(i=a;i>=b;i--)using namespace std;struct tuple{ll v; int t,PRe,p;} g;bool Operator<(tuple a,tuple b){return a.v<b.v;}priority_queue<tuple> q;int i,j,k,sp;ll n,t;int f[N],p[N];//當(dāng)前數(shù)、最大質(zhì)因數(shù)的次數(shù)、下一次選的質(zhì)因數(shù)的下標(biāo)的上限、最大質(zhì)因數(shù)的下標(biāo)int main(){ scanf("%lld%d",&n,&k); fo(i,2,128) if (!f[i]){p[++sp]=i;t=i;while(t<=128) f[t+=i]=1;} fo(i,1,sp) for (t = j = 1;(t * p[i]) <= n; j++) { t *= p[i]; q.push(tuple{(ll)t,j,i-1,i}); } while (k--) { g = q.top(); q.pop(); if (g.t > 1) { fd(i,g.pre,1) { ll u = g.v/p[g.p]*p[i]; q.push(tuple{(ll)u , g.t-1 , i , g.p}); } } } printf("%lld/n",g.v); return 0;}新聞熱點(diǎn)
疑難解答
