問題#
与えられた 2 つの正の整数 $n$ と $m$、および長さ $m$ の列 $a$ がある。
列から $k$ 個の数 $b_1,b_2,...,b_k$ を選び、$b_1 ! \times b_2 ! \times \cdots \times b_k !$ が $n!$ の因数となるような最大の $k$ を計算してください。
$100%$ のデータに対して、$1 \leq m,a_i \leq 2 \times 10^5$、$1 \leq n \leq 10^9$ です。
解法#
まずは暴力的な方法を考えますが、多くの問題が発生することがわかります。例えば、超 long long などの問題があるため、正解を考えます
ある性質に気づきます。小さな集合を選ぶ方が大きな集合を選ぶよりも優れているため、まず入力の $a$ をソートします。そして、$k$ を二分探索して、最初の $k$ 個が $n$ の因数であるかをチェックします。
ここで試験中に詰まってしまいました
大きな数が別の大きな数の因数であるかを判断するにはどうすればよいでしょうか —— 素因数分解です。
しかし、これほど大きな数に対して素因数を分解して保存するのは明らかに合理的ではないため、まずすべての素数を求めてから計算することを考えます —— エラトステネスの篩を使います。
私たちが篩い出した各素数について、$n!$ と $b_1 ! \times b_2 ! \times \cdots \times b_k !$ の素因数分解後の集合でそれぞれの出現回数を統計します。前者が後者より少ない場合は不可能です。以下の 2 つの問題に変換します。
- ある素数が $n!$ の素因数分解集合に何回出現するかを統計する方法
$n!$ には $p$ の倍数、$p^2$ の倍数、$p^3$ の倍数が出現する可能性があります。これをどう計算するのでしょうか？
$n! = 1 p * \cdots2p\cdots3p*\cdots*(n/p)*p$
次に $p^2$ ですが、その一部は $p$ の時に既に計算されているため、$n/=p$ として再計算するだけで済みます。このように繰り返し、最後にすべての結果を加算します。
- ある素数が $b_1 ! \times b_2 ! \times \cdots \times b_k !$ に何回出現するかを統計する方法
まず、
cnt配列を作成し、上式中の各数が何回出現したかを記録します。
その後、上記と同様に $p$ の倍数、$p^2$ の倍数、$p^3$ の倍数を見ます。
なお、素数の篩は最大の $a$ まで処理すれば十分です。
コード#
#include<bits/stdc++.h>
using namespace std;
#define maxn 200000
#define ll long long
const int N = 2e5 + 10;
int a[N], p[N], vis[N], cnt[N], tot;
int n, m;
int ask(int p, int n)
{
if(n == 0) return 0;
return n / p + ask(p, n / p);
}
bool check(int x)
{
memset(cnt, 0, sizeof cnt);
for(int i = 1;i <= x;i++)
cnt[a[i]]++;
for(int i = N - 2;i >= 0;i--)
{
cnt[i] += cnt[i + 1];
}
for(int i = 1;i <= tot;i++)
{
int c = ask(p[i], n);
long long b = 0;
for(int j = p[i]; j < N / p[i];j *= p[i])
{
for(int k = j;k < N;k += j)
{
b += cnt[k];
}
}
// cout << "qwq b:" << b << " c:" << c << endl;
if(b > c) return 0;
}
return 1;
}
//bool check(int x){
// memset(cnt,0,sizeof(cnt));
// for (int i=1;i<=x;i++)cnt[a[i]]++;
// for (int i=maxn;i>=1;i--)cnt[i]+=cnt[i+1];
// for (int i=1;i<=tot;i++){
// int c=ask(n,p[i]);
// ll d=0;
// for (int j=p[i];j<=maxn/p[i];j*=p[i]){
// for (int k=j;k<=maxn;k+=j)
// d+=cnt[k];
// }
// cout << "qwq b:" << d << " c:" << c << endl;
// if (d>c)return 0;
// }
// return 1;
//}
int main()
{
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for(int i = 1;i <= m;i++)
{
cin >> a[i];
}
sort(a + 1, a + 1 + m);
vis[0] = vis[1] = 1;
for(int i = 2;i < N;i++)
{
if(vis[i])
{
continue;
}
p[++tot] = i;
for(int k = 2 * i;k < N;k += i)
{
vis[k] = 1;
}
}
int l = 0, r = m;
// cout << check(1);
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(check(mid))
l = mid;
else
r = mid - 1;
}
printf("%d", l);
}