\(~~\)给定n个正整数和一个数k,问这n个数的阶乘之和能不能被k的阶乘整除 我们把连续几个数的阶乘可以分解成如下结果: \(~~~~~~~~~~~~~~~~~~~~~~~~~\)sum = 5*(3*2!) 通过如下过程我们就可以将低位阶乘转化为高位阶乘题目链接
题目大意:
既:(a\(_{1}\)!+a\(_{2}\)!+a\(_{3}\)!+....+a\(_{n}\)!)\(~\)%\(~\)k!\(~\)==$~$0
题目分析:
\(~~~\)假设现在有3个2,4个3:
\(~~~\)那我们可以得到sum\(~\)=$~$3*2!+ 4*(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;
}