解题思路

题目要求判断一个非负整数是否可以表示为若干个不同阶乘的和。例如，9可以表示为1! + 2! + 3!。解题的关键在于如何高效地验证这种可能性。

方法思路

1. 预处理阶乘数组：首先计算并存储所有可能的阶乘数，直到阶乘值超过题目给定的最大数1,000,000。经过计算，12!是不超过该值的最大阶乘数，因此预处理0到12的阶乘值。
2. 贪心策略验证：对于每个输入的数n，从最大的阶乘数开始尝试减去，如果减去后剩余值非负，则继续尝试减去下一个较小的阶乘数，直到剩余值为0或无法再减。如果最终剩余值为0，则说明n可以表示为若干阶乘的和。

解决代码

#include<iostream>
#define EQ 0
using namespace std;

int i_Factorial(int n)
{
    int temp=1;
    int m=1;
    while(m<=n)
    {
        temp=temp*m;
        m++;
    }
    return temp;
}

int main()
{
    int i,n,a[12];
    for(i=0;i<12;i++)
        a[i]=i_Factorial(i);
    while(1)
    {
        cin>>n;
        if(n==0)
        {
            cout<<"NO"<<endl;
            continue;
        }
        else if(n<0)
        {
            return 0;
        }
        i=11;
        while(i>=0 && n>0) 
        {
            if(n>=a[i]) n=n-a[i];
            i--;
        }
        if(n==0) 
            cout<<"YES"<<endl;
        else 
            cout<<"NO"<<endl;
    }//while
    return 0;
}

代码解释

1. 预处理阶乘数组：通过i_Factorial函数计算0到12的阶乘值，并存储在数组a中。
2. 输入处理：循环读取输入的非负整数n，直到遇到负数结束。
3. 贪心验证：对于每个n，从最大的阶乘数12!开始尝试，如果n大于等于当前阶乘值，则减去该值，继续尝试下一个较小的阶乘数，直到n变为0或无法再减。
4. 结果输出：根据最终n是否为0，输出"YES"或"NO"。

这种方法的时间复杂度为O(1)，因为预处理的阶乘数数组大小固定，且每次验证过程的操作次数也是固定的。空间复杂度同样为O(1)。