显然，本题等同于问取一些无平方因子数，使之乘积不超过$10^{10}$，问共有多少种取法。
令$f(n,m)$为将n写成一些不超过m的无平方因子数的乘积，则
$$f(n,m)=\sum_df(\frac{n}{d},d),$$
其中d取遍n的不查过m的无平方因子约数。接下来用与第193题类似的手段可以计算上述和式，最终结果是$457895958010$。
注：本题的具体实现仍较为繁琐，以下代码改编自官方论坛，其对筛法的实现（sieve，f和d，其中f(n)是不超过n的无平方因子数的总数）十分精悍，值得借鉴。
from collections import defaultdict
target=10**10
bound=100000
a,b,c=0,(bound-1)>>1,1
sieve=bytearray([0]) + bytearray([1])*b
while a<=b:
if sieve[c>>1]:
sieve[a::c]=bytearray((b-a)//c+1)
c+=2
a+=(c-1)<<1
g=[target//k for k in range(1,bound+1)]+list(range(bound-1,0,-1))
f={q:q-(q>>2) for q in g}
k,p=0,1
for s in sieve:
p+=k
k+=8
if s:
for q in g:
if q<p:
break
f[q]-=f[q//p]
d=defaultdict(int)
d[target]=1
res=f[target]-1
for n in range(2,bound+1):
if f[n]!=f[n-1]:
d,t=defaultdict(int),d
while t:
q,r=t.popitem()
while q>=n*n:
d[q]+=r
q//=n
res+=(f[q]-f[n-1])*r
print res
|
