查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转前置知识:杜教筛(包括狄利克雷卷积)数论分块欧拉函数 或 莫比乌斯函数(会杜教筛的大佬上述都会吧)欧拉函数卷积推导$$\sum{i=1}^n\sum{j=1}^n ijgcd(i,j)$$根据 $\sum\limits_{i|n}\varphi(n)=n$ ($1 * \varphi = Id$)$$= \sum{i=1}^n\sum{j=1}^n ij \sum_{k|i,k|j} \varphi(k)$$调换枚举顺序$$= \sum{k=1}^n \varphi(k) \sum{k|i,k|j}……