Responsive image

问题 H: 最小的k值

问题 H: 最小的k值

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 19
[提交][状态][讨论版][命题人:]

题目描述

现在给出一个正整数 n ，找到最小值 k 使得 n 可以表示为k个不同的强大的数字的和，或者说没有这样的数字 k.
强大的数字：2的幂或者是任意数阶乘。即2d 或 x! （x表示任意的非负数）
例：1，4，6 都是强大的数字，因为1=1！，4=22 和 6 =3！ ，而7，10，18不是。

输入描述

每个测试包括多个测试样例，每一行包括测试用例的数量 T （1≤T≤100）
一个测试用例只包括一行，包括一个整数 n (1≤n≤1012)

输出描述

对于每个测试用例，将最小值 k 输出。
如果不存在k个强大的数字的和为n，那么输出-1.

样例输入

4
7
11
240
17179869184

样例输出

2
3
4
1

提示

在第一个测试用例中，7可以表示为1+6，其中1和6是强大的数字。因为7不是一个强大的数，我们知道最小可能值k=2 .

在第二个测试用例中，11表示三个强大的数字之和11=1+4+6，我们可以证明没有两个或一个强大的数的和为11。

在第三个测试用例中，240可以表示为240=24+32+64+120.观察一下240=120+120不是有效的表示，因为强大的数字必须不同的 .

[提交][状态]
ACM算法攻关部