題目#
給定兩個正整數 $n$ 和 $m$，以及一個長為 $m$ 的序列 $a$。
請計算出最大的 $k$，使得能在序列中選出 $k$ 個數 $b_1,b_2,...,b_k$，滿足 $b_1 ! \times b_2 ! \times \cdots \times b_k !$ 是 $n!$ 的因數。
對於 $100%$ 的數據，$1 \leq m,a_i \leq 2 \times 10^5$，$1 \leq n \leq 10^9$。
題解#
首先考慮暴力，發現會出現很多問題，包括超 long long 等問題，所以考慮正解
觀察到一個性質，選小的集合一定比選大的集合更優，所以先把輸入的 $a$ 排個序，然後就可以二分 $k$，check 一下前 $k$ 個是否是 $n$ 的因數
然後我考場上就卡在這裡了
考慮一下，如何判斷一個大數是否是另一個大數的因數呢 —— 分解質因數
不過對於這麼大的數，分解並保存檢驗他的質因數顯然不太合理，於是我們考慮先把所有的質數求出來再來計算 —— 埃氏篩即可
對於我們篩出來的每一個質數，在 $n!$ 和 $b_1 ! \times b_2 ! \times \cdots \times b_k ! $ 的質因數分解後的集合中分別統計其出現了多少次，如前者小於後者則不可行。轉化成下面兩個問題
1. 如何統計一個質數在 $n!$ 的質因數分解集合中出現了幾次
$n!$ 中可能會出現 $p$ 的倍數，$p^2$ 的倍數，$p^3$ 的倍數，如何計算呢？
$n! = 1 p * \cdots2p\cdots3p*\cdots*(n/p)*p$
然後是 $p^2$，由於其的一部分已經在 $p$ 的時候算過了，所以我們只需讓 $n/=p$ 再次計算，以此類推，最後所有的結果相加即可
2. 如何統計一個質數在 $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);
}