阶乘的和

题目描述

给定一个非负整数 n,请你判断是否存在一些整数 xi,能够使得 n=∑1≤i≤txi!,其中 t≥1,xi≥0,xi=xj iff i=j。
iff 表示当且仅当。

输入格式

输入包含多组测试数据。
每组数据占一行,包含一个非负整数 n。
最后一行是一个负数,表示输入结束,无需处理。

输出格式

每组数据输出一行结果,如果 n 能表示为若干数的阶乘之和,则输出 YES,否则输出 NO。

数据范围

0≤n≤106,
每组输入最多包含 100 组数据。

输入样例:

9
-1

输出样例:

YES

解法

这道题目数据范围明确给定了小于1e6,那么最多我们就只能取到9的阶乘,因为10!= 3628800。因此,我们所有能组成的n是由0!~9!这些数值组成的集合。那么总共是10个数,不能不取数,因此总共是2^{10}-1种情况,我们可以利用二进制来枚举所有的情况,一个10位的二进制数,哪一位是1就取得对应的阶乘值,存入哈希表即可!

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;

unordered_set<int> hashtable;

int f[10];

int main()
{
    //预处理出0-9的阶乘能凑出的所有情况
    for(int i = 0; i<=9; i++)
    {
        f[i] = 1;
        for(int j = 1; j<=i; j++)
            f[i] *= j;
    }
    for(int i = 1; i<(1<<10); i++)
    {
        int cur = 0;
        for(int j = 0; j<10; j++)
            if(i>>j & 1)
                cur += f[j];
        hashtable.insert(cur);
    }
    int n;
    while(cin>>n, n>=0)
    {
        if(hashtable.find(n) == hashtable.end()) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。