jzoj6150

题意

给定(n)个不同的(a_i)，对于(i=1sim n)，求(F(a_{1...i}))
(f(n)=sumlimits_{i=1}^n sumlimits_{j=1}^n mu(ij))
(g(n)=sumlimits_{i=1}^n sumlimits_{j=1}^n ij[(i,j)=1])
(F(S)=sumlimits_{Tsubseteq S}f(gcd_{ain T}(a))prodlimits_{ain T}g(a))

做法

(f(n)=sumlimits_{i=1}^n i^2phi(i))
(g(n)=sumlimits_{i=1}^n mu(i)(sumlimits_{j=1}^{frac{n}{i}}mu(ij))^2)
令(f(n)=sumlimits_{d|n}h(d))
则(F(S)=sumlimits_{Tsubseteq S}(sumlimits_{d|gcd_{ain T}(a)}h(d))prodlimits_{ain T}g(a)=sum h(d)((prodlimits_{d|a}g(a)+1)-1))

由于(a)均不同，插入的时候考虑约数的贡献即可