【题解】51nod-1575-Gcd and Lcm
题目
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1575
题意
\(S(n)=\sum_{k=1}^n \sum_{i=1}^k \sum_{j=1}^k lcm(gcd(k,i), gcd(k, j))\)
题解
\[ \begin{eqnarray} f(n) &=& \sum_{i=1}^n \sum_{j=1}^n lcm(gcd(i,n), gcd(j,n)) \\ &=& \sum_{d_1|n} \sum_{d_2|n} lcm(d_1,d_2) \sum_{i=1}^{\frac n {d_1}} [i \perp \frac n {d_1}] \sum_{j=1}^{\frac n {d_2}} [j \perp \frac n {d_2}] \\ &=& \sum_{i|n} \sum_{j|n} lcm(i, j) \varphi(\frac n i) \varphi(\frac n j) \\ &=& \sum_{d|n} \frac 1 d \sum_{i|n} \sum_{j|n} ij \varphi(\frac n i)\varphi(\frac n j) [gcd(i,j)=d] \\ &=& \sum_{d|n} \frac 1 d \sum_{i|\frac n d} \sum_{j|\frac n d}d^2ij\varphi(\frac n {id}) \varphi(\frac n {jd})[i \perp j] \\ &=& \sum_{d|n} \frac n d \sum_{i|d} \sum_{j|d} ij\varphi(\frac di)\varphi(\frac dj)[i\perp j] \end{eqnarray} \]
\[ \begin{eqnarray} g(d) &=& \sum_{i|d} \sum_{j|d} ij \varphi(\frac d i) \varphi(\frac d j) [i \perp j] \\ h(d, k) &=&\sum_{i|\frac dk}\sum_{j|\frac dk} k^2ij \varphi(\frac d{ki})\varphi(\frac d {kj}) \\ &=& k^2 (\sum_{i|\frac dk} i\varphi(\frac d {ki}))^2\\ g(d) &=& \sum_{k|d}\mu(k)h(d,k) \\ &=& \sum_{t|d} \mu(\frac dt)h(d,\frac dt) \\ &=& \sum_{t|d}\mu(\frac dt) (\frac dt)^2(\sum_{i|t} i\varphi(\frac ti))^2 \\ \end{eqnarray} \]
\[ f=id*(\mu \cdot id_2) * (id*\varphi)^2 \]
上述推导没什么用，只需要打表就可以发现 \(f\) 是一个积性函数，于是只能回归最初的梦想。 \[ \begin{eqnarray} f(p^k) &=& \sum_{i=1}^{p^k} \sum_{j=1}^{p^k} lcm(gcd(i,n), gcd(j,n)) \\ &=& \sum_{i=0}^k \sum_{j=0}^k p^{\max\{i,j\}} \varphi(p^{k-i}) \varphi(p^{k-j}) \\ &=& \sum_{i=0}^k p^i \varphi(p^{k-i}) (2\sum_{j=0}^i \varphi(p^{k-j}) - \varphi(p^{k-i})) \\ &=& p^k(2p^k-1) + \varphi(p^k) \sum_{i=0}^{k-1} (2p^k-p^{k-i-1}-p^{k-i}) \\ &=& p^k(2p^k-1) + \varphi(p^k)(2kp^k - (p+1)\sum_{i=0}^{k-1} p^{k-i-1}) \\ &=& \cdots \\ &=& p^{k-1} + (2k+1)(p^{2k}-p^{2k-1})\\ f(p) &=& 3p^2-3p+1 \end{eqnarray} \] 可以 Min_25 筛直接搞。
1 |
|