阶乘之和
时间限制: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; }