n∑i=1lcm(i,n)=n∑d|nind∑i=1[gcd(nd,i)=1]=n∑d|nid∑i=1[gcd(d,i)=1]=n∑d|nid∑i=1∑j|gcd(d,i)μ(j)=n∑d|n∑j|dμ(j)d∑i=1i[j|i]=n∑d|n∑j|dμ(j)jdj∑i=1i=n∑d|n∑j|dμ(dj)djj(j+1)2=n2∑d|nd∑j|djμ(dj)=n2∑d|ndφ(d) 这里最后推出了dirichelet卷积的形式后面可以根据 φ=id1∗μ 直接推出最后的公式
根本不会!!! QAQ
根本不会!!! QAQ