阶乘之和

时间限制：3000 ms  |  内存限制：65535 KB

难度：3

 

描述

给你一个非负数整数n，判断n是不是一些数（这些数不允许重复使用，且为正数）的阶乘之和，如9=1！+2!+3!，如果是，则输出Yes，否则输出No；

 

输入

第一行有一个整数0<m<100,表示有m组测试数据；

每组测试数据有一个正整数n<1000000;

输出

如果符合条件，输出Yes，否则输出No;

样例输入

2910

样例输出

YesNo

#include
       
        int fun1(int n){	int i=1,s=1;	for(i=1;i<=n;i++)	{		s=s*i;		if(s==n)			return 1;		else if(s*(i+1)>n)		{			break;		} 			}	if(n>=2*s)		return 0;	else	{		n-=s;		fun1(n);	}}int main(){	int m;	scanf("%d",&m);	while(m--)	{		int n;		scanf("%d",&n);		if(fun1(n))			printf("Yes\n");		else			printf("No\n");	}}
       

这题不愧为贪心算法！我做这题做了两个小时，思路是对的，我就是没处理好阶乘时的问题才没做出来。S是小于等于整数N的第一最近N的某一个数的阶乘。我求这个S时犯了好多错误，千万不要让S=S/(i-1);那种形式，一定要干净利落的写出一个S否则就会出错。这题原理很简单，我们都知道N！必定大于前面N-1项阶乘的和，因为阶乘的倍数增长的太快了。加法就没法和它比，所以，我们就从S出发，当S*N>N-S>=S的时候，你感觉还会N还会是一些数的阶乘吗？肯定不会。如果S==N，那就说明正好有整数的阶乘与其相等，所以我利用递归让N=N-S；直到有N==S或者有N>=S的结果时就可以做出判断了！