现将小于1e6的数的阶乘初始化出来;
每一个数有两种情况, 选或者不选;
将dfs枚举出来的值用哈希表记录起来;
最后查表判断;
- dfs会将0也录进哈希表中, 但0不会由阶乘的和凑出, 因此要特判;
- 0!和1!都是1, 因此所有的阶乘中有两个1, 这里也要注意;
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int n;
vector<int> num;
map<int, bool> st;
void init()
{
num.push_back(1);
for(int i = 1, j = 1;j <= 1e6;i ++)
{
j *= i;
num.push_back(j);
}
}
void dfs(int u, int sum)
{
if(u >= num.size())
{
st[sum] = true;
return ;
}
dfs(u + 1, sum);
dfs(u + 1, sum + num[u]);
}
int main()
{
init();
dfs(0, 0);
while(cin >> n, n >= 0)
{
if(n && st[n]) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}