P3312 [SDOI2014]数表 - 《存代码》

$P3312 [SDOI2014]数表 - 图1$ %20%3D%26%20%5Csum%7Bi%3D1%7D%5En%20i%5Bi%7Cn%5D%20%5C%5C%0A%3D%26%20%5Csum%7Bd%7Cn%7D%20d%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%5Csigma%28n%29%20%3D%26%20%5Csum%7Bi%3D1%7D%5En%20i%5Bi%7Cn%5D%20%5C%5C%0A%3D%26%20%5Csum%7Bd%7Cn%7D%20d%0A%5Cend%7Baligned%7D%0A)

实际上也就是 $P3312 [SDOI2014]数表 - 图2$ 其中， $P3312 [SDOI2014]数表 - 图3$ 表示狄利克雷卷积。

题意：

$P3312 [SDOI2014]数表 - 图4$ %5D%20%5C%5C%20%0A%3D%26%5Csigma(%5Cgcd(i%2Cj))%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Clarge%0A%5Cbegin%7Baligned%7D%0Af%7Bij%7D%20%3D%26%20%5Csum%7Bd%3D1%7D%5E%7Bn%7D%20%5Bd%7Ci%5D%5Bd%7Cj%5D%20%5C%5C%0A%3D%26%5Csum_%7Bd%3D1%7D%5E%7Bn%7D%20%5Bd%7C%5Cgcd%28i%2Cj%29%5D%20%5C%5C%20%0A%3D%26%5Csigma%28%5Cgcd%28i%2Cj%29%29%0A%5Cend%7Baligned%7D%0A)

容易发现 $P3312 [SDOI2014]数表 - 图5$ 函数可以通过预处理获得
先不考虑 $P3312 [SDOI2014]数表 - 图6$ 的限制：

$P3312 [SDOI2014]数表 - 图7$ )%20%20%5C%5C%0A%3D%26%5Csum%7Bd%3D1%7D%5E%7Bn%7D%5Csum%7Bi%3D1%7D%5En%5Csum%7Bj%3D1%7D%5E%7Bn%7D%5Csigma(d)%5B%5Cgcd(i%2Cj)%3Dd%5D%20%5C%5C%0A%3D%26%5Csum%7Bd%3D1%7D%5E%7Bn%7D%5Csum%7Bi%3D1%7D%5En%5Csum%7Bj%3D1%7D%5E%7Bn%7D%5Csum%7Bd%7Ct%7D%5Cmu(%5Cdfrac%7Bt%7D%7Bd%7D)%5Csigma(d)%5Bt%7C%5Cgcd(i%2Cj)%5D%20%5C%5C%0A%3D%26%5Csum%7Bd%3D1%7D%5E%7Bn%7D%5Csum%7Bi%3D1%7D%5En%5Csum%7Bj%3D1%7D%5E%7Bn%7D%5Csum%7Bd%7Ct%7D%5Cmu(%5Cdfrac%7Bt%7D%7Bd%7D)%5Csigma(d)%5Bt%7Ci%5D%5Bt%7Cj%5D%20%5C%5C%0A%3D%26%5Csum%7Bt%3D1%7D%5E%7Bn%7D%5Csum%7Bi%3D1%7D%5En%5Bt%7Ci%5D%5Csum%7Bj%3D1%7D%5E%7Bn%7D%5Bt%7Cj%5D%5Csum%7Bd%7Ct%7D%5Cmu(%5Cdfrac%7Bt%7D%7Bd%7D)%5Csigma(d)%20%5C%5C%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Clarge%0A%5Cbegin%7Baligned%7D%0A%26%5Csum%7Bi%3D1%7D%5En%5Csum%7Bj%3D1%7D%5E%7Bn%7D%5Csigma%28%5Cgcd%28i%2Cj%29%29%20%20%5C%5C%0A%3D%26%5Csum%7Bd%3D1%7D%5E%7Bn%7D%5Csum%7Bi%3D1%7D%5En%5Csum%7Bj%3D1%7D%5E%7Bn%7D%5Csigma%28d%29%5B%5Cgcd%28i%2Cj%29%3Dd%5D%20%5C%5C%0A%3D%26%5Csum%7Bd%3D1%7D%5E%7Bn%7D%5Csum%7Bi%3D1%7D%5En%5Csum%7Bj%3D1%7D%5E%7Bn%7D%5Csum%7Bd%7Ct%7D%5Cmu%28%5Cdfrac%7Bt%7D%7Bd%7D%29%5Csigma%28d%29%5Bt%7C%5Cgcd%28i%2Cj%29%5D%20%5C%5C%0A%3D%26%5Csum%7Bd%3D1%7D%5E%7Bn%7D%5Csum%7Bi%3D1%7D%5En%5Csum%7Bj%3D1%7D%5E%7Bn%7D%5Csum%7Bd%7Ct%7D%5Cmu%28%5Cdfrac%7Bt%7D%7Bd%7D%29%5Csigma%28d%29%5Bt%7Ci%5D%5Bt%7Cj%5D%20%5C%5C%0A%3D%26%5Csum%7Bt%3D1%7D%5E%7Bn%7D%5Csum%7Bi%3D1%7D%5En%5Bt%7Ci%5D%5Csum%7Bj%3D1%7D%5E%7Bn%7D%5Bt%7Cj%5D%5Csum%7Bd%7Ct%7D%5Cmu%28%5Cdfrac%7Bt%7D%7Bd%7D%29%5Csigma%28d%29%20%5C%5C%0A%5Cend%7Baligned%7D%0A&height=322&width=336)

上述公式的 $P3312 [SDOI2014]数表 - 图8$ 代表的是一个终值，具体是 $P3312 [SDOI2014]数表 - 图9$ 需要具体讨论。

设 $P3312 [SDOI2014]数表 - 图10$ %20%3D%20%5Csum%7Bi%3D1%7D%5E%7Bn%7D%20%5Bt%7Ci%5D#card=math&code=f%28t%29%20%3D%20%5Csum%7Bi%3D1%7D%5E%7Bn%7D%20%5Bt%7Ci%5D)，则 $P3312 [SDOI2014]数表 - 图11$ %20%3D%20%5Clfloor%5Cdfrac%7Bn%7D%7Bt%7D%5Crfloor#card=math&code=f%28t%29%20%3D%20%5Clfloor%5Cdfrac%7Bn%7D%7Bt%7D%5Crfloor)
原式可以化为：

$P3312 [SDOI2014]数表 - 图12$ %5Csigma(d)%20%0A#card=math&code=%5Clarge%0A%5Csum%7Bt%3D1%7D%5E%7Bn%7D%5Clfloor%5Cdfrac%7Bn%7D%7Bt%7D%5Crfloor%20%5Clfloor%20%5Cdfrac%7Bm%7Dt%7B%7D%5Crfloor%5Csum%7Bd%7Ct%7D%5Cmu%28%5Cdfrac%7Bt%7D%7Bd%7D%29%5Csigma%28d%29%20%0A)

设 $P3312 [SDOI2014]数表 - 图13$ %20%3D%20%5Csum%7Bd%7Ct%7D%5Cmu(%5Cdfrac%7Bt%7D%7Bd%7D)%5Csigma(d)#card=math&code=g%28t%29%20%3D%20%5Csum%7Bd%7Ct%7D%5Cmu%28%5Cdfrac%7Bt%7D%7Bd%7D%29%5Csigma%28d%29)（ $P3312 [SDOI2014]数表 - 图14$ 卷 $P3312 [SDOI2014]数表 - 图15$ 可以容易筛出）

加入限制 $P3312 [SDOI2014]数表 - 图16$

$P3312 [SDOI2014]数表 - 图17$ %20%3D%20%5Csum%7Bd%7Ct%7D%5Cmu(%5Cdfrac%7Bt%7D%7Bd%7D)%5Csigma(d)%20(%5Csigma(d)%5Cge%20a)%0A#card=math&code=%5Clarge%0Ag%28t%29%20%3D%20%5Csum%7Bd%7Ct%7D%5Cmu%28%5Cdfrac%7Bt%7D%7Bd%7D%29%5Csigma%28d%29%20%28%5Csigma%28d%29%5Cge%20a%29%0A)

// Sigma 为排序之后的除数函数映射 
// lst 为上一次加入的位置 
for(int i = lst;i; --i){
    d = Sigma[i];
    if(d < a) break;
    for(int j=1;j * d <= N;++j)
        G[i * j] = d * Mu[j];
}

考虑将询问离线，按照 $P3312 [SDOI2014]数表 - 图18$ 排序，这样我们就可以逐次求出 $P3312 [SDOI2014]数表 - 图19$ 函数。
代回原式数论分块即可。