题目链接
题目大意：
\(~~\)给定n个正整数和一个数k，问这n个数的阶乘之和能不能被k的阶乘整除
既：(a\(_{1}\)!+a\(_{2}\)!+a\(_{3}\)!+....+a\(_{n}\)!)\(~\)%\(~\)k!\(~\)==$~$0
题目分析：
我们把连续几个数的阶乘可以分解成如下结果：
\(~~~\)假设现在有3个2,4个3：
\(~~~\)那我们可以得到sum\(~\)=$~$3*2！+ 4*(3*2!)
\(~~~~~~~~~~~~~~~~~~~~~~~~~\)sum = 5*(3*2!)
通过如下过程我们就可以将低位阶乘转化为高位阶乘
那最终我们其实求得就是m*(k!) % k! == 0
所以我们就需要将所有的低位阶乘全部转化为高位阶乘，如果中间有不能转换的部分(既剩余部分)，那就说明最终不能转化为k！的倍数，此时就为“No”
代码实现：
# include<iostream>
# include<bits/stdc++.h>
using namespace std;
# define int long long
# define endl "\n"
const int N = 5e5 + 10;
int a[N];
void solve() {
int n,k;
cin>>n>>k;
map<int,int> cnt; //计数
for(int i = 1;i <= n;++i){
cin>>a[i];
if(a[i]<k) cnt[a[i]]++;
}
for(int i = 1;i < k;++i){
if(cnt[i]%(i+1))//若不能整除说明转化的时候会有剩余，则输出No
{
cout<<"No"<<endl;
return;
}
cnt[i+1] += cnt[i]/(i+1);//低位转化到高位
}
cout<<"Yes"<<endl;
}
int tt;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
tt = 1;
// cin >> tt;
while (tt--)solve();
return 0;
}
![[NOI.AC省选模拟赛3.23] 集合 [数学]](https://www.kunjuke.com/file/css/thumb/6.jpg/280-180.jpg)
