阶乘之和
时间限制：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,从9的阶乘开始比较,如果大于9的阶乘,n就减去9的阶乘,然后继续和8的阶层比,如果小于8的阶乘,再和7的阶乘比,以此类推,大于就减去,小于就继续跟小的数比,比到1就知道yes或者no了
搜索的AC代码:
#include<stdio.h>
int num[10] = {1 , 2 , 6 , 24 , 120 , 720 , 5040 , 40320 , 362880 , 3628800};
int f(int n , int m)
{
int i ;
if(n == 0)
{
printf("Yes\n");
return 1;
}
if(m < 0 || n < 0)
return 0;
for(i = m ; i >= 0 ; i--)
{
if(f(n - num[i] , m - 1) == 1)
return 1;
}
return 0;
}
int main()
{
int i , j , k;
scanf("%d" , &i);
while(i--)
{
scanf("%d" , &j); for(k = 0 ; ; k++)
{
if(num[k] > j)
{
k--;
break;
}
}
if(f(j - num[k] , k- 1) == 0)
printf("No\n");
}
return 0;
}