Loj 2047 伪光滑数

正解较复杂,但这道题其实可以通过暴力解决.
预处理出 \(128\) 内的所有质数,把 \(n\) 内的 \(prime[i]^j\) 丢进堆中,再尝试对每个数变形,除一个质因子,再乘一个.
保证最大值因子的次数为正就可以了,取 \(k\) 次堆顶即得答案.

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define mp make_pair

#define pii pair<int,int>

inline ll read()

{

	ll x=0;

	bool pos=1;

	char ch=getchar();

	for(;!isdigit(ch);ch=getchar())

		if(ch=='-')

			pos=0;

	for(;isdigit(ch);ch=getchar())

		x=x*10+ch-'0';

	return pos?x:-x;

}

ll n,k;

struct node{

	ll a,b,c,d;

	node(ll a,ll b,ll c,ll d):a(a),b(b),c(c),d(d) {}

	bool operator < (const node &rhs) const

		{

			return a<rhs.a;

		}

};

bool isp(ll x)

{

    for(ll i=2;i*i<=x;++i)

        if(x%i==0)

			return false;

    return true;

}

priority_queue<node> hp;

ll pr[130],cnt=0;

int main()

{

	n=read(),k=read();

	for(ll i=2;i<=128;++i)

		{

			if(isp(i))

				{

					pr[++cnt]=i;

					ll a=1;

					for(ll j=1;a<=n/i;++j)

						{

							a*=i;

							hp.push(node(a,i,0,0));

							if(cnt>1 && j>1)

								hp.push(node(a/i*pr[cnt-1],i,j-1,cnt-1));

						}

				}

		}

	while(--k)

		{

			node cur=hp.top();

			hp.pop();

			ll a=cur.a,b=cur.b,c=cur.c,d=cur.d;

			if(d>1)

				hp.push(node(a/pr[d]*pr[d-1],b,c,d-1));

			if(c>1)

				hp.push(node(a/b*pr[d],b,c-1,d));

		}

	cout<<hp.top().a<<endl;

	return 0;

}

巴特西

Loj 2047 伪光滑数

Loj 2047 伪光滑数

最新文章

热门文章