题解 | #Sum of Factorials#

思路

There's a fact that the sum of factorials from to is strictly smaller than :

So when:

must be one of the . Otherwise, , which is contradicts to .

And if , then contains only .

So we can design the algorithm as follow

实现

#include <iostream>
#include <array>

using namespace std;

int main()
{
    std::array<int, 11> F; // F[i] = i!
    F[0] = 1;
    for (int i = 1; i < 11; i++)
    {
        F[i] = (i) * F[i-1];
    }

    int n;
    while (cin >> n) {
        for (int i = 10; i >= 0; i--) {
            if (F[i] <= n) {
                n -= F[i];
            }
            if (n == 0) {
                break;
            }
        }
        if (n == 0) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}