听说这道题标算是可持久化可并堆，但是用优先队列+贪心可以卡过去%%%。 首先找出所有小于128的质数，如果某个质数的q次方（q任取）小于n，那么这就是一个可行方案，加入优先队列。 接着每次取出一个方案，去掉一个质因数，加入一个较小的质因数，就形成了一个新的方案，加入队列，一直取k次即可。 具体实现方式是用一个四元组(x,i,j,k)表示一种方案，其中x表示当前的数；i那个最大的质因数的次数；j表示上一次加入的质因数，因为为了保证每一次方案不重复，加入的质因数必须越来越小；k表示最大的质因数。
#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];//当前数、最大质因数的次数、下一次选的质因数的下标的上限、最大质因数的下标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;}新闻热点
疑难解答
