题目描述
给定一个非负整数 $n$,请你判断是否存在一些整数 $x_i$,能够使得 $n=\sum_{i=1}^{t}{x_i!}$,其中 $t≥1,x_i≥0,x_i=x_j$ 当且仅当 $i=j$。
输入格式
输入包含多组测试数据。
每组数据占一行,包含一个非负整数 $n$。
最后一行是一个负数,表示输入结束,无需处理。
输出格式
每组数据输出一行结果,如果 $n$ 能表示为若干数的阶乘之和,则输出 YES
,否则输出 NO
。
数据范围
$0≤n≤10^6$,
每组输入最多包含 $100$ 组数据。
输入样例
9
-1
输出样例
YES
算法1
(二进制枚举)
- 常见数据:
9! = 362880
,10! = 3628800
- 预处理
0
到9
的阶乘,共十个数,并且全部存入数组。把每个数当成一个二进制位,问题则转化为用二进制枚举这个数组的子集,把所有可能的结果存入哈希表中去重,最后判断询问是否在哈希表中即可
Java 代码
import java.util.*;
public class Main{
public static void main(String[] args){
// 预处理阶乘
int[] f = new int[10];
f[0] = f[1] = 1;
for(int i = 2; i <= 9; i++) f[i] = f[i-1] * i;
Set<Integer> set = new HashSet<>();
for(int i = 0; i < 1 << 10; i++){
int sum = 0;
for(int j = 0; j < 10; j++){
if(((i >> j) & 1) == 1){
sum += f[j];
}
}
set.add(sum);
}
Scanner sc = new Scanner(System.in);
while(true){
int n = sc.nextInt();
if(n < 0) break;
if(n == 0) System.out.println("NO");
else System.out.println(set.contains(n) ? "YES" : "NO");
}
}
}
社区里JAVA的题解很少,感谢你!
你的题解写得真棒!
感谢支持~