835 字

4 分钟

阶乘

2023-09-30

oi

/

qbxt

题目#

给定两个正整数 $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 * \cdots*2*p*\cdots*3*p*\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$ 即可

代码#

1
#include<bits/stdc++.h>
2

3
using namespace std;
4
#define maxn 200000
5
#define ll long long
6
const int N = 2e5 + 10;
7
int a[N], p[N], vis[N], cnt[N], tot;
8
int n, m;
9

10
int ask(int p, int n)
11
{
12
  if(n == 0) return 0;
13
  return n / p + ask(p, n / p);
14
}
15

16
bool check(int x)
17
{
18
  memset(cnt, 0, sizeof cnt);
19
  for(int i = 1;i <= x;i++)
20
    cnt[a[i]]++;
21
  for(int i = N - 2;i >= 0;i--)
22
  {
23
    cnt[i] += cnt[i + 1];
24
  }
25

26
  for(int i = 1;i <= tot;i++)
27
  {
28
    int c = ask(p[i], n);
29
    long long b = 0;
30
    for(int j = p[i]; j < N / p[i];j *= p[i])
31
    {
32
      for(int k = j;k < N;k += j)
33
      {
34
        b += cnt[k];
35
      }
36
    }
37
//    cout << "qwq b:" << b << " c:" << c << endl;
38
    if(b > c) return 0;
39
  }
40
  return 1;
41
}
42

43
//bool check(int x){
44
//  memset(cnt,0,sizeof(cnt));
45
//  for (int i=1;i<=x;i++)cnt[a[i]]++;
46
//  for (int i=maxn;i>=1;i--)cnt[i]+=cnt[i+1];
47
//  for (int i=1;i<=tot;i++){
48
//    int c=ask(n,p[i]);
49
//    ll d=0;
50
//    for (int j=p[i];j<=maxn/p[i];j*=p[i]){
51
//      for (int k=j;k<=maxn;k+=j)
52
//        d+=cnt[k];
53
//    }
54
//    cout << "qwq b:" << d << " c:" << c << endl;
55
//    if (d>c)return 0;
56
//  }
57
//  return 1;
58
//}
59
int main()
60
{
61
    freopen("a.in", "r", stdin);
62
    freopen("a.out", "w", stdout);
63
  ios::sync_with_stdio(0), cin.tie(0);
64
  cin >> n >> m;
65
  for(int i = 1;i <= m;i++)
66
  {
67
    cin >> a[i];
68
  }
69
  sort(a + 1, a + 1 + m);
70
  vis[0] = vis[1] = 1;
71
  for(int i = 2;i < N;i++)
72
  {
73
    if(vis[i])
74
    {
75
      continue;
76
    }
77
    p[++tot] = i;
78
    for(int k = 2 * i;k < N;k += i)
79
    {
80
      vis[k] = 1;
81
    }
82
  }
83
  int l = 0, r = m;
84

85

86
//  cout << check(1);
87
  while(l < r)
88
  {
89
    int mid = (l + r + 1) >> 1;
90
    if(check(mid))
91
      l = mid;
92
    else
93
      r = mid - 1;
94
  }
95
  printf("%d", l);
96
}

阶乘

https://blog.histcat.top/posts/factorial/

作者

Histcat

发布于

2023-09-30

许可协议

CC BY-NC-SA 4.0

合并

等差