題目大意是給定一個數(shù)n，問約數(shù)個數(shù)為n的最小的數(shù)k是多少。其中1 <= n <= 10000, k <= 10 ^ 15。
這是一個經(jīng)典問題了，我一直以為會有經(jīng)典算法，開始的時候一直往貪心上想，結(jié)果owen給出了反例。后來經(jīng)過吉大牛點(diǎn)撥，因?yàn)閗 <= 10 ^ 15，可以根據(jù)這個定界，最差情況k的素因子也不會超過13，這樣就可以搜索了！
實(shí)現(xiàn)的時候我也犯了幾個小錯，一個是把10 ^ 15少打了一個0，還有一個剪枝必須加：如果當(dāng)前結(jié)果的約數(shù)個數(shù)為f，那么如果n % f不為0，則剪掉，因?yàn)榧s數(shù)個數(shù)是以乘積的關(guān)系累加的。
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 閱讀(297)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm - Number Theory