【BZOJ】1225: [HNOI2001] 求正整数

时间：2023-03-08 18:44:44

http://www.lydsy.com/JudgeOnline/problem.php?id=1225

题意：给一个数n，求一个最小的有n个约数的正整数。（n<=50000）

#include <bits/stdc++.h>

using namespace std;

struct inum {

	static const int N=10005, MOD=10000;

	int a[N], len;

	inum(int x=0) { len=!x; memset(a, 0, sizeof a); while(x) a[++len]=x%MOD, x/=MOD; }

	void fix() { while(len>1 && !a[len]) --len; }

	void cln() { memset(a, 0, sizeof(int)*(len+1)); len=1; }

	const bool operator< (const inum &x) const  {

		if(len<x.len) return 1;

		if(len>x.len) return 0;

		for(int i=len; i; --i)

			if(a[i]<x.a[i]) return 1;

			else if(a[i]>x.a[i]) return 0;

		return 0;

	}

	inum operator* (const inum &x) {

		static inum ret;

		ret.cln();

		for(int i=1; i<=len; ++i)

			for(int j=1; j<=x.len; ++j) {

				ret.a[i+j-1]+=a[i]*x.a[j];

				if(ret.a[i+j-1]>=MOD) ret.a[i+j]+=ret.a[i+j-1]/MOD, ret.a[i+j-1]%=MOD;

			}

		ret.len=len+x.len;

		for(int i=1; i<=ret.len; ++i)

			if(ret.a[i]>=MOD) ret.a[i+1]+=ret.a[i]/MOD, ret.a[i]%=MOD;

		ret.fix();

		return ret;

	}

	void P() {

		printf("%d", a[len]);

		for(int i=len-1; i; --i)

			printf("%.04d", a[i]);

	}

};

inum ipow(inum a, int n) {

	inum x=1;

	while(n) { if(n&1) x=x*a; a=a*a; n>>=1; }

	return x;

}

typedef long long ll;

vector<int> a[50005];

int p[17]={1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};

void init(int lim) {

	for(int n=2; n<=lim; ++n) if(lim%n==0) {

		for(int i=1; i*i<=n; ++i) if(n%i==0) { int j=n/i; a[n].push_back(i); if(j!=i) a[n].push_back(j); }

		sort(a[n].begin(), a[n].end());

	}

}

inum ans;

void d(int x, int n, int last, inum now) {

	if(n==1) { if(ans.len==0) ans=now; else ans=min(ans, now); }

	if(ans.len!=0 && !(now<ans)) return;

	inum t=p[x];

	for(int i=1; i<(int)a[n].size(); ++i)

		if(a[n][i]>last) break;

		else d(x+1, n/a[n][i], a[n][i], now*ipow(t, a[n][i]-1));

}

int main() {

	int n; scanf("%d", &n);

	init(n);

	ans.len=0;

	d(1, n, n, inum(1));

	ans.P(); puts("");

	return 0;

}

　　

比较水的题，由于搜索量很小，所以暴力= =（然而我的高精模板常数好大= =

相关文章