codeforces 300E Empire Strikes Back 数论+二分查找

题意：给定N个数a1,a2,a3...aN，现在要求最小的n满足 n!/(a1!*a2!*...*aN!) 是一个正整数的最小的n。

分析：这题的想法很明确，就是分解a1!*a2!*...*aN!，把其分解成质因子相乘的形式，这个都很熟悉了，然后就是对每一个质因子二分搜索出一个数字下界，最后求其中最大的一个数，问题的关键就是如何分解这样一个表达式成一个质因子相乘的形式。使用一个cnt数组来表示每一个数的在乘积中出现的次数，然后从后往前假设一个数出现了k次，那么如果这个数是素数则不用更新，如果一个数是合数则将其分解成两部分，一个是该数最小的质因子，一个是除以这个质因子之后的值，接着一直做下去，就能够把所有的素因子全部统计起来，最后再对每一个素因子都二分搜索。

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <set>

#include <cmath>

#include <vector>

using namespace std;

typedef long long LL;

const int N = ;

vector<int>vv;

LL cnt[N];

int p[N];

int Max;

LL sum;

int n;

void pre() {

    for (int i = ; i < N; ++i) {

        if (!p[i]) {

            p[i] = i;

            vv.push_back(i);

        }

        for (int j = ; i*vv[j] < N; ++j) {

            p[i*vv[j]] = vv[j];

            if (i % vv[j] == ) break;

        }

    }

}

LL cal(LL mid, LL base) {

    LL ret = ;

    while (mid) {

        ret += (mid /= base);

    }

    return ret;

}

void deal() {

    for (int i = Max; i >= ; --i) {

        if (p[i] != i) {

            cnt[p[i]] += cnt[i];

            cnt[i/p[i]] += cnt[i];

        }

    }

}

LL get(LL base, LL x) {

    LL l = , r = sum;

    LL ret;

    while (l <= r) {

        LL mid = (l + r) >> ;

        if (cal(mid, base) >= x) {

            ret = mid;

            r = mid - ;

        } else {

            l = mid + ;

        }

    }

    return ret;

}

int main() {

    pre();

    scanf("%d", &n);

    int x;

    for (int i = ; i < n; ++i) {

        scanf("%d", &x);

        sum += x;

        Max = max(Max, x);

        ++cnt[x];

    }

    for (int i = Max-; i >= ; --i) {

        cnt[i] += cnt[i+];

    } // 模拟阶乘，1-n之间每个数都有一个

    deal();

    LL ret = ;

    for (int i = ; i < vv.size(); ++i) {

        ret = max(ret, get(vv[i], cnt[vv[i]]));

    }

    printf("%I64d\n", ret);

    return ;

}

巴特西

codeforces 300E Empire Strikes Back 数论+二分查找

最新文章

热门文章