题解 | #RdecAgl#

套路题的嵌套。

首先只用对每个 $i=1,2,\dots ni=1,2,\; \backslash dots\; n$ 算 ${\sum }_T\gcd (T_1,\dots ,T_i)\backslash sum\_T\; \backslash gcd(T\_1,\; \backslash dots,\; T\_i)$，之后随便组合一下就能算出答案。

考虑数论分块，需要对所有 $\lfloor m\mathrm{/}d\rfloor \backslash lfloor\; m/d\; \backslash rfloor$ 相同的 $dd$ 求 $\phi (d)\backslash varphi(d)$ 的和，这一步可以用你喜欢的筛法(如min25筛)完成。

之后问题变成了对 $i=1,2,\dots ni=1,2,\; \backslash dots\; n$ 求 ${\sum }_{j=1}^G{a}_j{b}_j^i\backslash sum\_\{j=1\}^G\; a\_j\; b\_j^i$，$G\approx 2\sqrt{m}G\; \backslash approx\; 2\; \backslash sqrt\{m\}$。

${\sum }_{j=1}^G{a}_j{b}_j^i=[x^i]({\sum }_{j=1}^G{\displaystyle \frac{a_j}{1-b_{j}x}})\backslash sum\_\{j=1\}^G\; a\_j\; b\_j^i=[x^i](\backslash sum\_\{j=1\}^G\; \backslash dfrac\{a\_j\}\{1-b\_jx\})$，所以只需分治NTT即可。