Solution
首先， 是不可能的。因为任意一个非负整数都可以转换成对应的二进制。而对应二进制位上的 ，单独拿出来，就都是强数。
比如 。
那么，现在就想，如何使 （即分解个数）最小了。
若直接枚举强数相加，那么时间复杂度为 。比较危险。
但是，发现只要确定阶乘的强数，反过来就可以推出二次幂的强数个数。
所以，可以只枚举 次就可以了。
（ 来自何方？ 的逆阶乘小于等于 。）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<bits/stdc++.h>
using namespace std;
int minx=-1;
long long a[17];
long long fac(int x)
{
long long ans=1;
for(int i=1;i<=x;i++) ans*=i;
return ans;
}
void init()
{
for(int i=1;i<=16;i++) a[i]=fac(i);
}
int bitcount(long long x)
{
int ans=0;
do
ans+=(x&1);
while(x>>=1);
return ans;
}
void dfs(int now,int tot,long long sum)
{
if(now==16+1||sum-a[now]<0)
{
minx=min(minx,tot+bitcount(sum));
return;
}
dfs(now+1,tot+1,sum-a[now]);
dfs(now+1,tot,sum);
}
int main()
{
init();
int t;
cin>>t;
while(t--)
{
long long n;
int ans=0;
minx=1e9;
cin>>n;
dfs(1,0,n);
cout<<minx<<endl;
}
return 0;
}
|