简化题面: 求
[T = sum_{i=1}^{n}sum_{j=1}^{lfloor frac{n}{i}
floor}sum_{k=1}^{j}[gcd(j,k)=1]
]
[T = sum_{i=1}^{n}sum_{j=1}^{lfloor frac{n}{i}
floor}varphi(j)
]
令
[S(n) = sum_{i=1}^{n}varphi(i)
]
则
[egin{align*}
T &= sum_{i=1}^{n}S(lfloor frac{n}{i}
floor) \
&= S(n) + sum_{i=2}^{n}S(lfloor frac{n}{i}
floor) \
end{align*}]
令
[f=varphi,g=I,h=f*g=Id
]
由杜教筛，
[g(1)S(n)=sum_{i=1}^{n}h(i)-sum_{i=2}^{n}g(i)S(lfloor frac{n}{i}
floor) \
herefore S(n)=frac{n(n+1)}{2}-sum_{i=2}^{n}S(lfloor frac{n}{i}
floor) \
herefore T = frac{n(n+1)}{2}-sum_{i=2}^{n}S(lfloor frac{n}{i}
floor) + sum_{i=2}^{n}S(lfloor frac{n}{i}
floor) = frac{n(n+1)}{2} \
]