Empire Strikes Back
题目描述
给定 \(k\) 个数 \(a_1,a_2,\dots,a_k\)，求一个数 \(p=n!\) 使得 \(p\) 能被 \(\prod_{i=1}^ka_i!\) 整除。
\(a_i\le 10^7,k\le 10^6\)
Solution
考虑先对 \(\displaystyle\prod\limits_{i=1}^ka_i!\) 分解质因数。假设分解出来为 \(\displaystyle\prod\limits_{i=1}^tp_i^{k_i}\)，那么显然可以直接二分找到 \(p\)，因为一定存在 \(p_i\le 10^7\)。这部分容易做到 \(\mathcal O(n\log n)\) 的复杂度，即直接筛出 \(10^7\) 之内的所有质数 \(p_i\)，然后枚举 \(p_i\) 的所有次幂并计算其贡献。
考虑怎么对 \(\displaystyle\prod\limits_{i=1}^ka_i!\) 分解质因数，直接暴力对每个数分解然后加起来显然是不行的。发现 \(a_i!\) 其实可以看做是一个区间的数乘起来，那么可以使用差分与处理出每个数出现了多少次，然后使用和上面一样的做法，枚举 \(p_i\) 的每一个次幂，然后遍历所有的 \(p_i\mid d\)，将 \(d\) 出现的次数贡献进 \(p_i\) 的贡献。
时间复杂度大概是比 \(n\log^2 n\) 小的多的，具体多少不会算（逃。
Code
// Cirno is not baka!
#include <bits/stdc++.h>
#define For(i, a, b) for (int i = (a); i <= (int)(b); ++i)
#define Rof(i, a, b) for (int i = (a); i >= (int)(b); --i)
#define FILE(filename) { \
freopen(#filename ".in", "r", stdin); \
freopen(#filename ".out", "w", stdout); \
}
#define All(x) x.begin(), x.end()
#define rAll(x) x.rbegin(), x.rend()
#define pii pair<int, int>
#define fi first
#define se second
#define i64 long long
#define i128 __int128_t
#define mkp make_pair
// #define int long long
#define epb emplace_back
#define pb push_back
using namespace std;
const int _N = 1e6 + 5, mod = 1e9 + 7, inf = 1e9, _M = 1e7 + 5;
template<typename T> void Max(T &x, T y) {x = max(x, y);}
template<typename T> void Min(T &x, T y) {x = min(x, y);}
namespace BakaCirno {
bitset<_M> flag;
vector<int> prim;
vector<i64> cnt;
void InitPrime(int n) {
For(i, 2, n) {
if (!flag[i]) prim.epb(i);
for (int j : prim) {
if (j * i > n) break;
flag[j * i] = 1;
if (i % j == 0) break;
}
}
cnt.resize(prim.size(), 0);
}
int N, A[_M];
void _() {
InitPrime(1e7);
cin >> N; A[0] = N;
int mx = 0;
For(i, 1, N) {
int x; cin >> x; Max(mx, x);
A[x + 1] -= 1;
}
For(i, 1, mx) A[i] += A[i - 1];
For(i, 0, prim.size() - 1) for (i64 j = prim[i]; j <= mx; j *= prim[i])
for (int k = j; k <= mx; k += j)
cnt[i] += A[k];
i64 L = 1, R = 1e15;
auto Check = [&](i64 x)->bool {
vector<i64> tcnt(prim.size(), 0);
For(i, 0, prim.size() - 1) for (i128 j = prim[i]; j <= x; j *= prim[i])
tcnt[i] += x / j;
For(i, 0, prim.size() - 1)
if (tcnt[i] < cnt[i]) return 0;
return 1;
};
while (L <= R) {
i64 mid = (L + R) >> 1;
if (Check(mid)) R = mid - 1;
else L = mid + 1;
}
cout << L << '\n';
}
}
signed main() {
// FILE(test);
cin.tie(0)->sync_with_stdio(0); int T = 1;
// cin >> T;
while (T--) BakaCirno::_();
// fout.flush();
}