BZOJ 1225: [HNOI2001] 求正整数( dfs + 高精度 )

时间:2021-09-25 15:39:29

BZOJ 1225: [HNOI2001] 求正整数( dfs + 高精度 )

15 < log250000 < 16, 所以不会选超过16个质数, 然后暴力去跑dfs, 高精度计算最后答案..

------------------------------------------------------------------------------

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
 
using namespace std;
 
const int maxn = 50009;
const int n = 16;
const int p[n] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
 
int N, ans[n], g[n], ansn;
double cur = 1e30;
 
void dfs(int x, int lim, double res, int cnt) {
if(res > cur) return;
if(cnt == N) {
if(res < cur) {
ansn = x;
for(int i = 0; i < x; i++) ans[i] = g[i];
cur = res;
}
} else {
if(x == n) return;
for(int i = 0; i <= lim; i++) if(cnt * (i + 1) <= N) {
g[x] = i;
dfs(x + 1, i, res + i * log(p[x]), cnt * (i + 1));
}
}
}
 
struct Int {
static const int base = 10000;
static const int width = 4;
static const int maxn = 1000;
int s[maxn], n;
Int() {
n = 0;
memset(s, 0, sizeof s);
}
Int(int x) {
n = 0;
for(; x; x /= base) s[n++] = x % base;
}
Int operator = (const Int &o) {
n = o.n;
memcpy(s, o.s, sizeof(int) * n);
return *this;
}
Int operator * (const Int &o) const {
Int ret; ret.n = n + o.n - 1;
for(int i = 0; i < n; i++)
for(int j = 0; j < o.n; j++) 
ret.s[i + j] += s[i] * o.s[j];
for(int i = 0; i < ret.n; i++) if(ret.s[i] >= base) {
ret.s[i + 1] += ret.s[i] / base;
ret.s[i] %= base;
}
for(int &i = ret.n; ret.s[i]; i++) if(ret.s[i] >= base) {
ret.s[i + 1] += ret.s[i] / base;
ret.s[i] %= base;
}
return ret;
}
void write() {
int buf[width], c;
for(int i = n; i--; ) {
c = 0;
for(int t = s[i]; t; t /= 10) buf[c++] = t % 10;
if(i != n - 1)
for(int j = width - c; j--; ) putchar('0');
while(c--) putchar(buf[c] + '0');
}
puts("");
}
};
 
int main() {
scanf("%d", &N);
dfs(0, N - 1, 0, 1);
Int res = 1;
for(int i = 0; i < ansn; i++) {
Int _p = p[i];
for(int j = 0; j < ans[i]; j++)
res = res * _p;
}
res.write();
return 0;
}

------------------------------------------------------------------------------

1225: [HNOI2001] 求正整数

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 576  Solved: 232
[Submit][Status][Discuss]

Description

对于任意输入的正整数n,请编程求出具有n个不同因子的最小正整数m。例如:n=4,则m=6,因为6有4个不同整数因子1,2,3,6;而且是最小的有4个因子的整数。

Input

n(1≤n≤50000)

Output

m

Sample Input

4

Sample Output

6

HINT

Source

Dp