阶乘之和
时间限制：3000 ms | 内存限制：65535 KB
难度：3
- 描述
-
给你一个非负数整数n，判断n是不是一些数（这些数不允许重复使用，且为正数）的阶乘之和，如9=1！+2!+3!，如果是，则输出Yes，否则输出No；
- 输入
- 第一行有一个整数0<m<100,表示有m组测试数据；
每组测试数据有一个正整数n<1000000; - 输出
- 如果符合条件，输出Yes，否则输出No;
- 样例输入
-
2
9
10
- 样例输出
-
Yes
No
- 上传者
- 李剑锋
由于判断n是不是一些数的阶乘之和，这些数只要不一样，可以任意组合，没有连续和个数的限制，所以不可能穷举，那会很耗时。
不过经过思考发现阶乘有这么个性质：1!+2!+……+（k-1）!<k!，显而易见成立。
当k!<n<(k+1)!时，n必须包含k!，不然，比k小的所有阶乘之和都会小于n。
那这样，接下来就是寻找阶乘之和为n-k!的数了，接着寻找比n-k!小的最大阶乘即可，一直到1!。
#include
<iostream>02.using namespace std;03. 04.int fact[10]={1,2,6,24,120,720,5040,40320,362880};05. 06.int main()07.{08.int m,n,flag;09.cin>>m;10.while(m--)11.{12.cin>>n;13.int tmpn=n;14.flag=false;15.for(int i=9;i>=0;i--)16.{17.if(tmpn==fact[i])18.{19.flag=true;20.break;21.}22.else if(tmpn>fact[i])23.tmpn-=fact[i];24.}25.if(flag)26.cout<<"Yes"<<endl;27.else28.cout<<"No"<<endl;29.}30.return 0;31.}