拆分n的阶乘

125 阅读 0 评论 83 点赞

我是靠谱客的博主潇洒菠萝，最近开发中收集的这篇文章主要介绍拆分n的阶乘，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给你一个非负整数n，判断n是否为一些数（这些数不可以重复使用，且为整数）的阶乘之和，如9=1！+2！+3！，如果是，输出yes，否则输出no。

输入：第一行有一个正整数m，接下来的m行，每行一组测试数据，每组测试数据只有一个数字n。

输出：m行，yes或no。

#include<bits/stdc++.h>
using namespace std;
int main(){
int shu[10]={};
int ct[1000]={};
int s=1;
for(int i=1;i<=9;i++){
	shu[i]=s*i;
	s=s*i;
}
int m;
cin>>m;
for(int k=0;k<m;k++){
	int ct[1000]={};
int n;
cin>>n;
for(int i=1;i<=9;i++){
	if(shu[i]>n){
		break;
	}
	for(int j=n;j>=shu[i];j--){
		ct[j]=max(ct[j],ct[j-shu[i]]+shu[i]);
	}
}
if(ct[n]==n){
	cout<<"Yes";
}else{
	cout<<"No";
}}
	return 0;
}