「Bzoj 1053」「HAOI2007」反素数ant (因数个数 + 打表 / DFS)

发表于 | 分类于 | | + s

Bzoj 1053
题意：见上。

本题就是一个打表的典型题。但是打表程序很有学问否则你离开考场都打不完表。
最容易想到$O(n \sqrt n)$的暴力，但是对于$2 \times 10^{9}$太慢了。
我们可以运用这个定理：

给出n的唯一分解式 $n = p^{a1}_1p^{a2}_2p^{a3}_3…p^{ak}_k$ , 求出 $n$ 的正约数的个数
根据乘法原理，$n$ 的正约数的个数为
$\prod_{i=1}^{k}(a_i+1)$

然后就可以打质数表进行分解因数。我们发现一个$2 \times 10^{9}$以内的数字不会有超过$12$个质因子，并且小素因子多一定比大素因子多要优，预处理出前$12$个质数即可。

打完表输出即可。打表直接打出反素数即可，反素数个数很少。

生成器 (500s+​ 能完成)：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

using namespace std;

namespace flyinthesky {  

    LL pri[50] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71};

    void clean() {
    }
    int solve() {
        clean();
        freopen("1.out", "w", stdout);
        LL maxn = 0ll;
        for (LL i = 1ll; i <= 2000000000ll; ++i) {
            LL tmp = 1ll, whw = i;
            for (LL j = 0ll; j < 20ll; ++j) {
                LL gg = 0ll, x = pri[j];
                while (whw % x == 0ll) whw /= x, ++gg;
                tmp *= (gg + 1ll);
            }
            if (tmp > maxn) printf("%lld ", i);
            maxn = max(tmp, maxn);
        }
        printf("maxn=%lld\n", maxn);
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

打表：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

using namespace std;

namespace flyinthesky {  

    int atp[500] = {1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560, 10080, 15120, 20160, 25200, 27720, 45360, 50400, 55440, 83160, 110880, 166320, 221760, 277200, 332640, 498960, 554400, 665280, 720720, 1081080, 1441440, 2162160, 2882880, 3603600, 4324320, 6486480, 7207200, 8648640, 10810800, 14414400, 17297280, 21621600, 32432400, 36756720, 43243200, 61261200, 73513440, 110270160, 122522400, 147026880, 183783600, 245044800, 294053760, 367567200, 551350800, 698377680, 735134400, 1102701600, 1396755360, 2000001000};

    void clean() {
    }
    int solve() {
        clean();
        int n; scanf("%d", &n);
        for (int i = 1; ; i++) {
            if (atp[i] > n && atp[i - 1] <= n) return printf("%d\n", atp[i - 1]);
        }
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

正解DFS剪枝：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL pri[15] = {2, 3, 5, 7, 11, 13, 17, 19, 23};

    LL n, ans, ans_ys;

    void dfs(LL a, LL cur, LL ys, LL lstexp) {
        if (cur <= n) {
            if (cur > ans && ys > ans_ys) ans_ys = ys, ans = cur; 
            if (cur <= ans && ys >= ans_ys) ans_ys = ys, ans = cur;     
        }
        if (a > 8) return ;
        LL bs = 1, hh = 0;
        for (; cur * bs <= n && hh <= lstexp; bs *= pri[a], ++hh) {
            dfs(a + 1, cur * bs, ys * (hh + 1), hh);
        }
    }

    void clean() {
        ans = 0, ans_ys = 0;
    }
    int solve() {

        clean(); 
        scanf("%lld", &n);

        dfs(0, 1, 1, 1000000000);

        printf("%lld\n", ans);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------