题目大意是给定一个数n，问约数个数为n的最小的数k是多少。其中1 <= n <= 10000, k <= 10 ^ 15。
这是一个经典问题了，我一直以为会有经典算法，开始的时候一直往贪心上想，结果owen给出了反例。后来经过吉大牛点拨，因为k <= 10 ^ 15，可以根据这个定界，最差情况k的素因子也不会超过13，这样就可以搜索了！
实现的时候我也犯了几个小错，一个是把10 ^ 15少打了一个0，还有一个剪枝必须加：如果当前结果的约数个数为f，那么如果n % f不为0，则剪掉，因为约数个数是以乘积的关系累加的。
1 #include <cstdio>
2 const int M = 14;
3 const long long max = 1000000000000000LL;
4
5 int p[M] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41}, k;
6 long long ans;
7 void solve(long long v, int factor, int pos)
8 {
9 if (factor >= k)
10 {
11 if (factor == k) ans <?= v;
12 return;
13 }
14 if (k % factor) return;
15 if (pos == M) return;
16 for (int i = 1; i <= 50; i++)
17 {
18 v *= p[pos];
19 if (v > max) break;
20 solve(v, factor * (i + 1), pos + 1);
21 }
22 }
23
24 int main()
25 {
26 while (scanf("%d", &k) == 1)
27 {
28 ans = max + 1;
29 solve(1, 1, 0);
30 if (ans > max) printf("-1\n");
31 else printf("%lld\n", ans);
32 }
33
34 return 0;
35 }
36
posted on 2009-03-30 21:44
sdfond 阅读(290)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm - Number Theory