题解 | A题推导解

题面 $\\$ $求\sum_{i=1}^n \sum_{j=1}^{i} phi(j) \times \lfloor \frac{i}{j} \rfloor \\$ $设g(n)=\sum_{i=1}^n \sum_{j=1}^{i} phi(j) \times \lfloor \frac{i}{j} \rfloor \\$ $设h(n)=g(n)-g(n-1) =\sum_{i=1}^n phi(i) \times \lfloor \frac{n}{i} \rfloor \\$ $设v(n)=h(n)-h(n-1) =\sum_{i=1}^n phi(i) \times \lfloor \frac{n}{i} \rfloor - \sum_{i=1}^{n-1} phi(i) \times \lfloor \frac{n-1}{i} \rfloor \\$ $v(n)=phi(n) + \sum_{i=1}^{n-1} phi(i) \times (\lfloor \frac{n}{i} \rfloor - \lfloor \frac{n-1}{i} \rfloor) \\$ $\ \ \ \ \ \ \ \ \ =phi(n) + \sum_{i=1}^{n-1} phi(i) \times (\sum_{d=1}^{n}[d \times i\leq n] -\sum_{d=1}^{n-1}[d \times i\leq n-1])\\$ $\ \ \ \ \ \ \ \ \ =phi(n) + \sum_{i=1}^{n-1} phi(i) \times ([i==1]+\sum_{d=1}^{n-1}([d \times i\leq n]-[d \times i\leq n-1]))\\$ $\ \ \ \ \ \ \ \ \ =phi(n) + \sum_{i=1}^{n-1} phi(i) \times ([i==1]+\sum_{d=1}^{n-1}[d \times i ==n])\\$ $发现可以写成\\$ $\ \ \ \ \ \ \ \ \ =phi(n) + \sum_{i=1}^{n-1} phi(i) \times \sum_{d=1}^{n}[d \times i ==n]\\$ $\ \ \ \ \ \ \ \ \ =\sum_{i=1}^{n} phi(i) \times \sum_{d=1}^{n}[d \times i ==n]\\$ $\ \ \ \ \ \ \ \ \ =\sum_{i|n} phi(i) \\$ $= n$ $即v(n)=n \\$ $即g(n)=\sum_{i=1}^{n}\sum_{j=1}^{i}j \\$ $\ \ \ \ \ \ \ \ \ =\sum_{i=1}^{n}\frac{i \times (i+1)}{2} \\$ $\ \ \ \ \ \ \ \ \ =\frac{1}{2}(\sum_{i=1}^{n}i +\sum_{i=1}^{n}i^2)\\$ $\ \ \ \ \ \ \ \ \ =\frac{1}{2}(\frac{n \times (n+1) \times (2n+1)}{6} + \frac{n \times (n+1)}{2}) \\$ $\ \ \ \ \ \ \ \ \ =\frac{n \times (n+1) \times (n+2)}{6}\\$ $中间可能有写错的地方，望各位大佬指正 (代码很简单就不放了\\$

题解 | A题 推导解

题解 | A题推导解