莫比乌斯函数$\mu(n)$的定义如下：

若n是无平方因子数，则$\mu(n)=(-1)^{\omega(n)}$，其中$\omega(n)$是n的不同质因数的个数。

若n不是是无平方因子数，则$\mu(n)=0$。

令$P(a,b), N(a,b)$分别为区间$[a,b]$上使得$\mu(n)=1$和$\mu(n)=-1$的n的个数。例如$P(2,10)=2, N(2,10)=4$。

令$C(n)$为满足如下条件的整数对$(a,b)$的数量： $$1\le a\le b\le n, \quad 99N(a,b)\le100P(a,b), \quad 99P(a,b)\le100N(a,b). $$ 可以验证$C(10)=13, C(500)=16676, C(10000)=20155319$。

求$C(20000000)$。

本题难度:

解答

原条件可以转换为$199|P(a,b)-N(a,b)|\le P(a,b)+N(a,b)$，注意到$P(1,n)-N(1,n)$和$P(1,n)+N(1,n)$分别是$\mu(n)$以及$|\mu(n)|$的部分和，因此可以在生成$\mu$后分别记录这两者的对应关系。

若$S_n$和$S_n'$分别是$\mu(n)$以及$|\mu(n)|$的部分和，那么当$n$取遍$1$到$20000000$时，$S_n$可能出现的值远小于$20000000$（只有$2800$多个），用一个字典$d$记录每个$S_n$的取值所可能对应的$S_n'$的值的列表。

遍历此字典，设若$s_1,s_2$是$S_n$的可能取值，若$s_1=s_2$，那么显然条件始终满足，否则对$d[s_1]$中的每个值，二分查找$d[s_2]$中能满足条件的值即可。

最终结果是$198775297232878$。

注：因使用sympy生成莫比乌斯函数列表，以下代码为Python 3，代码中还打印了进度信息。此外，本题数据量较大，需要十多个小时的运行时间。

from bisect import bisect_left
from sympy import sieve

N=20000000

d={0:[0]}
c=s=0
for m in sieve.mobiusrange(1,N+1):
    s+=m
    if m:
        c+=1
    if s in d:
        d[s].append(c)
    else:
        d[s]=[c]
print("initialization completed, start computing...")

res=0
for i,a in enumerate(d):
    res+=sum(len(d[a])*(len(d[a])-1)//2 if a==b else len(d[b])*len(d[a])-sum(bisect_left(d[b],k+199*abs(b-a)) for k in d[a]) for b in d)
    print(f"{i}/{len(d)} completed, current sum: {res}")

print(res)