Lcm(a,b)表示a和b的最小公倍数，A(n)表示Lcm(n,i)的平均数(1 <= i <= n)，
例如：A(4) = (Lcm(1,4) + Lcm(2,4) + Lcm(3,4) + Lcm(4,4)) / 4 = (4 + 4 + 12 + 4) / 4 = 6。
F(a, b) = A(a) + A(a + 1) + ...... A(b)。(F(a,b) = ∑A(k), a <= k <= b)
例如：F(2, 4) = A(2) + A(3) + A(4) = 2 + 4 + 6 = 12。
给出a,b，计算F(a, b)，由于结果可能很大，输出F(a, b) % 1000000007的结果即可。
应该说这道的式子是比较好推的？感觉跟暴力差不多
由于A题几天后才写的题解，只是粗略地重推了一下，如果题解有误请谅解并指出……什么时候想起来我就改
求区间的话我们先考虑$F(x)$的前缀和再舍弃一部分就好了。
要求平均的话其实就是把$frac{i*j}{gcd(i,j)}$改成$frac{j}{gcd(i,j)}$而已
$$sum_{i=1}^{n} F(n)=sum_{i=1}^{n}sum_{j=1}^{i}frac{j}{gcd(i,j)}$$
$$=sum_{d=1}^{n} sum_{i=1}^{frac{n}{d}} sum_{j=1}^{i} [gcd(i,j)==1]*j$$
$$=sum_{d=1}^{n} sum_{d'=1}^{frac{n}{d}} sum_{i=1}^{frac{n}{d*d'}} sum_{j=1}^{i} j*d'*μ(d')$$
$$=sum_{d=1}^{n} sum_{d'=1}^{frac{n}{d}} d'*μ(d')* sum_{i=1}^{frac{n}{d*d'}} sum_{j=1}^{i} j$$
$$=sum_{d=1}^{n} sum_{d'=1}^{frac{n}{d}} s(d')* sum_{i=1}^{frac{n}{d*d'}} frac{x(x+1)}{2}$$
$$=sum_{d=1}^{n} sum_{d'=1}^{frac{n}{d}} s(d')*f(frac{n}{d*d'})$$
其中$s(x)=x*μ(x)$，$f(x)=frac{x(x+1)(2x+1)}{12}+frac{x(x+1)}{4}$
完事用分段计算的方法处理一波
$s(x)$的前缀和就杜教筛搞定：$s(x)=1-sum_{i=2}^{n} i*s(leftlfloorfrac{n}{i}
ight
floor)$
就这样。
一开始我就是这样直接$F(b)-F(a-1)$的，然后T了……
压常压一半被家长喊去睡觉……然后在床上想到在计算F(x)的时候直接做差，就不用跑两次了。于是硬是在床上用手机A掉了……
代码太丑不贴辣。