AcWing 3481. 阶乘的和
原题链接
简单
作者:
上下四方
,
2025-01-15 11:41:28
,
所有人可见
,
阅读 1
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int func(int x) {
if (x == 0 || x == 1) {
return 1;
}
else {
return x * func(x - 1);
}
}
int main() {
vector<int> factorialArr;
for (int i = 0; i <= 9; i++) {
factorialArr.push_back(func(i)); //10!>1000000 故记录9!即可。开一个数组记录0!~9!
}
set<int> all; //记录阶乘和的所有情况
all.insert(0); //初始化,插入零
for (int i = 0; i <= 9; i++) { //枚举,每次选择一个阶乘加入集合
set<int> cur = { 0 }; //用一个当前插入的集合记录,必须,否则会陷入死循环
for (set<int>::iterator it = all.begin(); it != all.end(); it++) {
cur.insert(*it + factorialArr[i]);
}
for (set<int> ::iterator it = cur.begin(); it != cur.end(); it++) {
all.insert(*it); //再将当前集合插入所有情况的集合
}
}
all.erase(0);
int n;
while (scanf("%d", &n) != EOF) {
if (n < 0) {
break;
}
if (all.count(n) == 0) {
printf("NO\n");
}
else {
printf("YES\n");
}
}
return 0;
}