正题
题目链接:http://www.51nod.com/Challenge/Problem.html#problemId=1227
题目大意
定义
\[F(a)=\frac{\sum_{i=1}^a lcm(a,i)}{a}
\]
给出\(l,r\)求\(\sum_{i=l}^rF(i)\)
解题思路
好久没做数论题了
直接拆成两个前缀和的差，然后有
\[\sum_{i=1}^n\sum_{j=1}^i\frac{j}{gcd(i,j)}
\]
\[\sum_{d=1}^n\frac{1}{d}\sum_{i=1}^n\sum_{j=1}^ij[gcd(i,j)=d]
\]
\[\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{i}j[gcd(i,j)=1]
\]
\[\frac{1}{2}+\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\frac{\varphi(i)i}{2}
\]
函数\(H(n)=\varphi(n)n\)可以用杜教筛，\(H\times id\)就可以得到\(n^2\)的函数。
code
#include
#include
#include
#include