C语言 阶乘之和

来源：百度知道 编辑：UC知道 时间：2024/05/01 22:09:55
有些数能若干个数的阶乘之和。例如，数字9，9=1！+2！+3！。给定一个数n（n<=1,000,000），判断它是否能表示成若干个数的阶乘之和。注意，这些数不一定是连续的，也不一定从1开始。

输入描述
输入数据有多组，每组占一行，由一个整数组成，直到输入-1结束。

输出描述
对于每组输入数据，输出一行。如果能表示成阶乘之和，输出“YES”，否则输出“NO”。

输入样例
0 1 2 9 10 12 24 5040 -1

输出样例
NO YES YES YES YES NO YES YES

//---------------------------------------------------------------------------
/*2009-12-4
by wxd11011*/
#include <stdio.h>
#include <stdlib.h>
#define OUT 1 /*这里的两个宏用于控制是否输出详细情况*/
#define NOOUT 0
long int jcx(int n) /*返回n的阶乘*/
{
long int j=1;
int i;
if (n>1) {
for (i = 1; i<=n; i++) {
j*=i;
}
}
return j;
}
int chk(long int n,unsigned int b,int isout) /*判断是否存在不小于b的若干整数，使得这些整数的阶乘之和等于n，isout用于控制是否输出详细情况，如果传入的是OUT，则输出找到的整数*/
{
long int i,j;
int flag=0;
static int *ys=NULL;

if (!ys) {
ys=calloc(2,sizeof(int));
ys[0]=1;
}
else{
ys[0]++;
ys=realloc(ys,sizeof(int)*(ys[0]+1));
}
for (i = b; i<=n; i++) {
j=jcx(i);

ys[ys[0]]=i;
if (n-j>0) {

flag=chk(n-j,i+1,isout);
}
else if (n-j==0) {
flag=1;
}<