阶乘和的问题
典型的用空间换时间
将0-9之内的所有阶乘和记录到set中,共1024个
单纯的遍历
//阶乘的和
#include<iostream>
#include<unordered_set>
#include<set>
using namespace std;
//求x的阶乘
long long f(int x){
if(x==0) return 1;
else{
x=x*f(x-1);
}
return x;
}
int main(){
int n;//9!=362880>=1e6,8!=40320,故i<=8cout<<"NO"<<endl;
int a[10];
for (int i =0;i<=9; i++) a[i]=f(i);
//所有阶乘和的可能性
set<int> all_possible;
all_possible.insert(0);
for(int i=0;i<=9;i++){
set<int> temp;
set<int>::iterator it;
for(it=all_possible.begin();it!=all_possible.end();it++){
temp.insert(*it+a[i]);
}
for(it=temp.begin();it!=temp.end();it++) all_possible.insert(*it);
}
all_possible.erase(0);
while(cin>>n){
if(n<0) break;
if(all_possible.count(n)==0) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}