本题的关键是统计第i行中不能被i+1到m之间的数整除的项的数量，而这可以在遍历i时记忆化完成，最终结果是$258381958195474745$。
注：因使用cache装饰器作记忆化搜索，以下代码为Python 3。
import math
from functools import *
m=64
n=10**16
primes=(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61)
f=lambda L,a,b:a if b==0 or a < L[b-1] else a-sum(f(L,a//L[j],j) for j in range(b))
@cache
def check(n,S):
if len(S)==0:
return n
R = set()
for x in S:
for y in S:
if x>y and x%y==0:
break
else:
R.add(x)
for p in primes:
if len(D:=[x for x in R if x%p==0])>1:
C=tuple([x for x in R if x%p>0])
B=tuple([x//p for x in D]+[x for x in R if x%p>0])
return check(n,C)-check(n//p,C)+check(n//p,B)
L=sorted(R,reverse=True)
res=f(L,n,len(L))
return res
print(sum(check(n,tuple(set(j//math.gcd(i,j) for j in range(i+1,m+1)))) for i in range(1,m+1)))
|
