题目描述
给定一个非负整数 n，请你判断 n 是否可以由一些非负整数的阶乘相加得到。
输入格式
有若干组数据。每行一个整数 n，保证 n<1000000。 以负数结束输入。
输出格式
对于每组数据输出一行，若可以则输出‘YES’，否则输出‘NO’。
输入输出样例
输入 #1
9 -1
输出 #1
YES
7/20 校内测模拟T3
差点就离（lì）开（kǎi）这个右袖的湍堆了
四道题两道模拟可是还是只特么100分WDNMD
话不多说这篇博客是为了UOJ题解水的
我的想法是枚举全排列
我们通过计算（打表）可得
1！ = 1
2！ = 2
3！ = 6
4！ = 24
5！ = 120
6！ = 720
7！ = 5040
8！ = 40320
9！ = 362880
10! = 3628800
最后别忘了0！ = 1（惨死于此
等一下...
这数据范围...
n<1000000
我直接疑天下之大惑
那就是说数据只可能由0到9的阶乘构成
那我们考虑用一个10位二进制数表示选择情况
那只有1024种可能
同时用桶排思想开个420000（这十个阶乘加起来不超过420000）的布尔数组
将这1024种情况与处理出来便可以完成O（1）查询了
代码如下
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <cmath> #include <set> #include <cstdlib> using namespace std; int no[430000]; void find() { long long n; cin>>n; if(n < 0) exit(0); if(n == 0) { cout<<"NO"<<endl; find(); } if(n > 420000) { cout<<"NO"<<endl; find(); } if(no[n] == true) { cout<<"YES"<<endl; find(); } if(no[n] != true) { cout<<"NO"<<endl; find(); } } int main() { for(int a = 0; a <= 1; a++) for(int b = 0; b <= 1; b++) for(int c = 0; c <= 1; c++) for(int d = 0; d <= 1; d++) for(int e = 0; e <= 1; e++) for(int f = 0; f <= 1; f++) for(int g = 0; g <= 1; g++) for(int h = 0; h <= 1; h++) for(int i = 0; i <= 1; i++) for(int j = 0; j <= 1; j++) { unsigned long long sum = 0; if(j == 1) sum += 1; if(i == 1) sum += 1; if(h == 1) sum += 2; if(g == 1) sum += 6; if(f == 1) sum += 24; if(e == 1) sum += 120; if(d == 1) sum += 720; if(c == 1) sum += 5040; if(b == 1) sum += 40320; if(a == 1) sum += 362880; no[sum] = true; } find(); }
原文链接: https://www.cnblogs.com/Jiangxingchen/p/13345640.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/368840
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
