阶梯序列

设有长度为n且满足$a_1=6$以及 $$\varphi(a_i) < \varphi (a_{i+1}) < a_i < a_{i+1},$$ 的序列，其中$\varphi$是欧拉Totient函数。

记$S(N)$为满足$a_n\le N$的此类序列的数量。例如，$S(10)=4$，因为有且仅有$\{6\}, \{6, 8\}, \{6, 8, 9\}, \{6, 10\}$这样四个满足要求的序列。

可以验证$S(100)=482073668$以及$S(10000) \bmod 10^8=73808307$。

求$S(20000000) \bmod 10^8$。

本题难度:

解答

序列中相邻的两数间有相互限制关系，因此可令$f(i)$为满足$a_1=i$且$a_n\le N$的序列总数，则有 $$f(i)=1+\sum_{\varphi(i) < \varphi(j) < i < j} f(j)$$ 以及初值$f(N)=1$。

令$N=20000000$递推计算，最后取$f(6)$再模余即得结果$85068035$。

target=20000000
s=[0]*(target+1)
f=[0]*(target+1)
phi=[i for i in range(target+1)]
m=100000000

lastBit=lambda x: x&(-x)

def cal(p):
    r=0
    k=p
    while k>0:
        r=(r+s[k])%m
        k-=lastBit(k)
    return r

for i in range(2, target+1):
    if phi[i]==i:
        for j in range(i,target+1,i):
            phi[j]=(phi[j]/i)*(i-1)

for i in range(target,5,-1):
    w=(cal(i-1)-cal(phi[i])+1)%m
    j=phi[i]
    while j < target+1:
        s[j]=(s[j]+w)%m
        j+=lastBit(j)
    f[i]=w
    if i%200000==0:print i/200000,"percent to be done"

print f[6]