数学、根号分治、整除分块

缺乏注意力导致的，本文用 $f$ 代替题面中的 $\operatorname{rev}$ 函数。

首先注意到 $n<p$ 时 $f(n,p) = n$，所以 $k \leq 10^{18}$ 这个范围是假的，能够计算 $\sum\limits_{i=2}^{n} f(n,i)$ 即可完成全部做法。

另外注意到 $\sum\limits_{i=2}^{\sqrt{n}} f(n,i)$ 可以暴力计算。

然后我到此为止了，缺乏注意力导致的。

注意到 $\sqrt{n} < p$ 时 $n$ 的 $p$ 进制表示只有两位，分别是 $\left\lfloor \dfrac{n}{p} \right\rfloor$ 和 $n \bmod p$，前者在数值表示中要乘上一个 $p$，推式子。

$$\sum_{i=\sqrt{n} + 1}^{n} f(n,i) = \sum_{i=\sqrt{n} + 1}^{n} \left( \left\lfloor \dfrac{n}{i} \right\rfloor + n \bmod i \times i \right)$$

公式化地把取模拆成乘除法组合。

$$= \sum_{i=\sqrt{n} + 1}^{n} \left( \left\lfloor \dfrac{n}{i} \right\rfloor + \left(n - \left\lfloor \dfrac{n}{i} \right\rfloor i \right) \times i \right)$$

$$= \sum_{i=\sqrt{n} + 1}^{n} \left( \left\lfloor \dfrac{n}{i} \right\rfloor + ni - \left\lfloor \dfrac{n}{i} \right\rfloor i \times i \right)$$

$$= \sum_{i=\sqrt{n} + 1}^{n} \left\lfloor \dfrac{n}{i} \right\rfloor + n \sum_{i=\sqrt{n} + 1}^{n} i - \sum_{i=\sqrt{n} + 1}^{n} \left\lfloor \dfrac{n}{i} \right\rfloor i^2$$

整除分块，瓶颈在 $\sum\limits_{i=2}^{\sqrt{n}} f(n,i)$ 的计算，总体时间复杂度 $O(\sqrt{n} \log n)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int mod=1'000'000'007;
constexpr Mint<mod> I(1);
Mint<mod> ans;
int n,k,lim;
long long m;
Mint<mod> rev(int x,int y){
    static int w[30];
    Mint<mod> ret(0);
    int cnt=0;
    while(x) w[++cnt]=x%y,x/=y;
    for(int i=1;i<=cnt;i++) ret=ret*y+w[i];
    return ret;
}
inline Mint<mod> one(int l,int r){
    return I*(r-l+1);
}
inline Mint<mod> squ(int l,int r){
    Mint<mod> ret=I*r*(r+1)*(2*r+1)/6;
    ret-=I*(l-1)*l*(2*(l-1)+1)/6;
    return ret;
}
Mint<mod> calculate(int x,Mint<mod> (*sum)(int,int)){
    Mint<mod> ret(0);
    for(int l=1,r=1;l<=x;l=r+1){
        r=min(n/(n/l),x);
        ret+=sum(l,r)*(n/l);
    }
    return ret;
}
void solution(){
    cin>>n>>m,k=min(1ll*n,m);
    lim=sqrt(n);
    ans=max(m-n,0ll)%mod*n;
    for(int i=2;i<=min(lim,k);i++) ans+=rev(n,i);
    if(lim<k){
        ans+=calculate(k,one)-calculate(lim,one);
        ans+=I*n*((lim+1)+k)*(k-(lim+1)+1)/2;
        ans-=calculate(k,squ)-calculate(lim,squ);
    }
    cout<<ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}