Codeforces-1753B Factorial Divisibility题解

Codeforces-1753B Factorial Divisibility

　　参考：https://blog.csdn.net/qq_38236082/article/details/127500190

　　题意：问$a_1!+a_2!+a_3!+...+a_n!$能否被$x!$整除。

　　思路：暴力肯定不行的，$x!$无法正常存储。考虑其他做法，由于$x!=x*(x-1)*(x-2)*...*2*1$，要想能被$x!$整除，和中一定存在这$x$个因子。

　　举一个例子，假设给定的数是$2!$,$2!$,$4!$,$5!$，$x=5$。

　　对于$2!+2!+4!+5!$，我们先拆出一部分因子$2!$，这部分因子是必定存在于最终的和中的。左边除去$2!$后我们剩下什么？剩下$1+1+3*4+3*4*5$，很容易发现，这部分不能够被$3$整除，也就是说，剩余的这一部分不存在$3$这个因子（而$3$这个因子是存在于$x!$中的！）。因此这个例子不能被$x$整除。

　　如果要求其能被$x!$整除，应该是什么样的数据呢？很容易想到，对于（上面那个例子）左边除去$2!$后，只有剩下的部分能够被$3$整除，这个判断才能够继续下去。因此我们更改数据为$2!$,$2!$,$2$,$4!$,$5!$，$x=5$。此时除去$2!$后，剩余$1+1+1+3*4+3*4*5$，可以被$3$整除。我们继续拆去$3$这个因子，除去$3$剩余$1+4+4*5$，判断出还是不行。但是我们已经基本了解了应该怎么判断——先对$a[n]排序，$取$cnt[i]$，记录这一串和中，$i!$的个数，随后从扫描$1~(x-1)$，对于数$i$，$cnt[i]$如果不是$i+1$的倍数（即不能提供出$i+1$因子），就直接判断不能整除；如果是倍数，我们将$cnt[i]/(i+1)$加到$cnt[i+1]$上。

　　由于注意到$n$非常大，我们还可以浅浅开个小快读，但不是必要。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=5e5;
const int maxx=5e5;

int n,x;
int a[maxn+5];
int cnt[maxx+5];

inline int read(){
    register int ch=getchar(),x=0,f=1;
    while (ch<'0'||ch>'9'){
        if (ch=='-')    f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

int main(){
//    freopen("1.txt","r",stdin);
    n=read(),x=read();
    for (int i=1;i<=n;i++)
        cnt[a[i]=read()]++;
    sort(a+1,a+n+1);
    for (int i=1;i<x;i++)
        if (cnt[i]%(i+1)){
            printf("No");
            return 0;
        }
        else
            cnt[i+1]+=(cnt[i]/(i+1));
    printf("Yes");
    return 0;
}