【u239】整数分解

Time Limit: 1 second

Memory Limit: 128 MB

【问题描述】

某些数能表示成为一些互不相同的整数的阶乘之和。如9=l!+2! +3!。现在给定一个非负整数n,要求判断n能否表示成为一些互不相同的非负整数的阶乘之和,如果能,则输出“YES",否则输出“N0”(引号不输出)。

【输入格式】

输入文件中每行一个非负整数n(n≤1000000),最后一行是一个负数,作为输入的结束。

【输出格式】

对输入文件中的每个非负整数n,在输出文件中分别输出“YES”或“N0”,各占l行。(引号不输出)

【数据规模】

Sample Input1

【题解】

对于n >=3；n!> (n-1）！+（n-2）!+(n-3)!....

eg:

0！=1 1！=1 2！=2 3！= 6

3 !>0!+1!+2!

根据这个原理，我们可以从9递减到1进行枚举。（10！>100W），只要这个数字能够减去i!，则一定要减。否则后面的数加起来都不能和i!一样大。因此规则就是遇到能减就减。

如果减完一次i!之后还能再减同样的i!，那么就无解了(要求数字要不同);最后判断一下答案是否为0就好。

n<=2的情况是

2 1 1,如果2可以减，那么就减。剩下两个1，可以一个一个减。又都是整数。所以如果有解，是一定不会漏掉的。

【代码】

#include <cstdio>

#include <cstring>

#define maxn 19

int n,a[11];

void input_data()

{

	a[0] = 1;

	for (int i = 1;i <= 10;i++) //先预处理出1!-10!的值存在a数组中

		a[i] = a[i-1] *i;

	int x;

	scanf("%d",&x); //输入数字，如果不为负数就继续.

	while (x >= 0)

		{

			int temp = x;

			bool flag = true;

			for (int i = 9;i >=0;i--) //进行枚举

				{

					if (temp >= (a[i+1] + 10)) //如果减完上一个数字还能继续减上一个数字，就输出无解

						{

							flag = false;

							break;

						}

					if (temp >= a[i]) //如果能减就减。不能减的就跳过。

						temp-=a[i];

				}

			if (flag && temp == 0 && x!=0) //如果刚好减完就输出有解信息。

				printf("YES\n");

					else

						printf("NO\n");

			scanf("%d",&x);

		}

}

int main()

{

	input_data();

	return 0;

}

巴特西