设
$$n=2^{a_1}3^{b_1}+\ldots+2^{a_m}3^{b_m},$$
若$a_i=a_j$，则$2^{a_i}3^{b_i}$和$2^{a_j}3^{b_j}$中较小的项必能整除较大的项，与要求不符。
因此2的幂一定互不相同，同理3的幂也一定互不相同。
不妨设$a_1 < \ldots < a_m$，则此时必有$b_1>\ldots>b_m$，否则仍将有能互相整除的项。
记$f(n,a,b)$为对数i的分割中满足$a_m\le a$且$b_m\ge b$的方法总数。
给定$(n,a,b)$，只需枚举不超过b的c，并将$f(n,a,b)$转移给$f(n+2^{a+1}3^{c},a+1,c)$即可，这表示每种满足$a_m\le a$且$b_m\ge b$的n的分割中再增加一项$2^{a+1}3^{c}$，就是一种满足$a_m\le a+1$且$b_m\ge c$的$n+2^{a+1}3^{c}$的分割。
可以写成$2^a3^b$形式的n的初值为1，其余为0，枚举n,a,b按上述方式转移即使得最终结果$3053105$。
import math
target=1000000
bound=14
d=[[] for i in range(36)]
f=[[0]*bound for i in range(target+1)]
visited=[False]*(target+1)
p=[0]*80000
m=0
for i in range(2,target):
if not visited[i]:
m+=1
p[m]=i
for j in range(i*i,target,i):
visited[j]=True
for i in range(36):
x=(1 << i)
while x < target:
d[i].append(x)
x*=3
f[0][bound-1]=1
for i in range(36):
for j in range(target,-1,-1):
for k in range(bound):
if f[j][k]>0:
for x in range(len(d[i])):
if x < k and j+d[i][x] <=target:
f[j+d[i][x]][x]+=f[j][k]
print(sum(p[i] for i in range(1,m+1) if sum(f[p[i]][j] for j in range(bound))==1))
|
