分析
-
因为 $9!=362880, 10! = 3628800$,$10!$已经大于$10 ^ 6$,因此我们只需要考虑
0~9
的阶乘即可。 -
我们可以首先求出
0~9
的阶乘,存入数组f
中,然后用位运算枚举出这10
个阶乘可以凑出的所有数,存入一个哈希表S
中,最后我们读入数据,判断读入的数据是否在哈希表中即可。
代码
#include <iostream>
#include <unordered_set>
using namespace std;
int f[10];
unordered_set<int> S;
int main() {
// 9! = 362880, 10! = 3628800
for (int i = 0; i < 10; i++) {
f[i] = 1;
for (int j = i; j > 0; j--)
f[i] *= j;
}
for (int i = 1; i < 1 << 10; i++) {
int s = 0;
for (int j = 0; j < 10; j++)
if (i >> j & 1)
s += f[j];
S.insert(s);
}
int n;
while (cin >> n, n >= 0) {
if (S.count(n))
puts("YES");
else
puts("NO");
}
return 0;
}