Problem#
Given two positive integers $n$ and $m$, and a sequence $a$ of length $m$.
Please calculate the maximum $k$ such that we can select $k$ numbers $b_1,b_2,...,b_k$ from the sequence, satisfying that $b_1 ! \times b_2 ! \times \cdots \times b_k !$ is a divisor of $n!$.
For $100%$ of the data, $1 \leq m,a_i \leq 2 \times 10^5$, $1 \leq n \leq 10^9$.
Solution#
First, consider brute force, but it turns out to have many issues, including exceeding long long, so we consider the correct approach.
Observe a property: selecting a smaller set is definitely better than selecting a larger set, so we first sort the input $a$, and then we can binary search $k$ to check if the first $k$ numbers are a divisor of $n$.
Then I got stuck here during the exam.
Consider how to determine if a large number is a divisor of another large number—factorization into prime factors.
However, for such large numbers, it is clearly unreasonable to factor and store to check its prime factors, so we consider first calculating all the primes and then computing—using the Sieve of Eratosthenes.
For each prime we sieve out, we count how many times it appears in the prime factorization set of $n!$ and $b_1 ! \times b_2 ! \times \cdots \times b_k !$ respectively; if the former is less than the latter, it is not feasible. This transforms into the following two problems:
- How to count how many times a prime appears in the prime factorization set of $n!$
In $n!$, multiples of $p$, multiples of $p^2$, multiples of $p^3$ may appear; how to calculate this?
$n! = 1 p * \cdots2p\cdots3p*\cdots*(n/p)*p$
Then for $p^2$, since part of it has already been counted when $p$ was considered, we only need to let $n/=p$ and calculate again, and so on, finally summing all the results.
- How to count how many times a prime appears in $b_1 ! \times b_2 ! \times \cdots \times b_k !$
First, we create a
cntarray to record how many times each number appears in the above expression.
Then, similarly, we look at multiples of $p$, multiples of $p^2$, multiples of $p^3$.
Additionally, note that we only need to sieve primes up to the largest $a$.
Code#
#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);
}