首先推式子:
\[\begin{aligned} ans&=\sum\limits_{i=A}^B\sum\limits_{j=1}^i\{\dfrac{i}{j}\} \end{aligned} \]考虑差分,设
\[f(n)=\sum\limits_{i=1}^n\sum\limits_{j=1}^i\{\dfrac{i}{j}\} \]那么
\[ans=f(B)-f(A-1) \]考虑如何计算 \(f(n)\):
\[\begin{aligned} f(n)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^i\{\dfrac{i}{j}\}\\ &=\sum\limits_{i=1}^n\sum\limits_{j=1}^i\dfrac{i}{j}-\lfloor\dfrac{i}{j}\rfloor\\ &=\sum\limits_{i=1}^ni·\sum\limits_{j=1}^i\dfrac{1}{j}-\sum\limits_{i=1}^n\sum\limits_{j=1}^n\lfloor\dfrac{i}{j}\rfloor\\ \end{aligned} \]如果设 \(s_i=\sum\limits_{j=1}^i\dfrac{1}{j}\),那么减号前面的东西可写作 \(\sum\limits_{i=1}^ni·s_i\),一遍前缀和求出。下面着重考虑减号右边的东西:
\[\begin{aligned} \sum\limits_{i=1}^n\sum\limits_{j=1}^n\lfloor\dfrac{i}{j}\rfloor \end{aligned} \]然后就是此题一个比较亮眼的地方了,考虑对 \(\lfloor\dfrac{i}{j}\rfloor\) 进行等价转化,不难发现 \(\lfloor\dfrac{i}{j}\rfloor=\sum\limits_{j\mid k}[k\le i]\),于是乎原式改写为:
\[\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{k\mid j}[k\le i] \]考虑每个 \(k\) 会对多少对 \((i,j)\) 产生贡献,显然符合条件的 \(i\) 的个数为 \((n+1-i)\),\(j\) 的个数为 \(d(k)\),其中 \(d\) 为约数个数和函数,那么上式可进一步写作:
\[\sum\limits_{k=1}^n(n+1-k)·d(k) \]维护 \(d(k),k·d(k)\) 的前缀和即可快速计算上式。
如果您比较勤快使用线性筛求解 \(d\) 那么时间复杂度为 \(\mathcal O(n)\),而我比较懒所以直接调和级数枚举,复杂度 \(n\log n\)。
using namespace fastio;
const int MAXN=1e6;
int inv[MAXN+5],s[MAXN+5],ss[MAXN+5],d[MAXN+5],sd[MAXN+5],ssd[MAXN+5];
void init(){
for(int i=(inv[0]=inv[1]=1)+1;i<=MAXN;i++) inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=MAXN;i++) s[i]=(s[i-1]+inv[i])%MOD,ss[i]=(ss[i-1]+1ll*s[i]*i)%MOD;
for(int i=1;i<=MAXN;i++) for(int j=i;j<=MAXN;j+=i) d[j]++;
for(int i=1;i<=MAXN;i++) sd[i]=(sd[i-1]+d[i])%MOD,ssd[i]=(ssd[i-1]+1ll*i*d[i])%MOD;
}
int calc(int x){return (ss[x]-(1ll*(x+1)*sd[x]%MOD-ssd[x]+MOD)%MOD+MOD)%MOD;}
int main(){
init();int qu;read(qu);
while(qu--){
int l,r;read(l);read(r);
printf("%d\n",(calc(r)-calc(l-1)+MOD)%MOD);
}
return 0;
}