题解

题解

我是真的不明白这玩意儿是怎么跟反演扯上关系的……

首先

\[ \begin{align} ans &=b\sum_{d|b}{1\over d}\sum_{i=a}^{b}i[\gcd(i,b)=d]\\ &=b\sum_{d|b}\sum_{i=\lceil{a\over d}\rceil}^{b\over d}i[gcd(i,{b\over d})=1]\\ \end{align} \]

然后有一个非常神仙的操作……就是强行反演一波，把\([n=1]\)化成\(\sum_{i|n}\mu(i)\)

\[ \begin{align} ans &=b\sum_{d|b}\sum_{i=\lceil{a\over d}\rceil}^{b\over d}i\sum_{j|\gcd(i,{b\over d})}\mu(j)\\ &=b\sum_{d|b}\sum_{j|{b\over d}}\mu(j)\sum_{i=\lceil{a\over d}\rceil}^{b\over d}[i \mod j=0]\\ &=b\sum_{d|b}\sum_{j|{b\over d}}\mu(j)\sum_{i=\lceil{a\over d}\rceil}^{b\over d}[i \mod j=0]\\ &={b\over 2}\sum_{d|b}\sum_{j|{b\over d}}\mu(j)j(\lfloor{b\over {dj}}\rfloor+\lceil{a\over {dj}}\rceil)(\lfloor{b\over {dj}}\rfloor-\lceil{a\over {dj}}\rceil+1)\\ &={b\over 2}\sum_{T|b}(\lfloor{b\over T}\rfloor+\lceil{a\over T}\rceil)(\lfloor{b\over T}\rfloor-\lceil{a\over T}\rceil+1)\sum_{d|T}\mu(d)d\\ \end{align} \]

那么我们只要把\(b\)分解一下质因数，然后\(dfs\)找出\(b\)的所有因子就可以了

然而这里还有一个问题，就是\(f(T)=\sum_{d|T}\mu(d)d\)该怎么快速计算

首先我们可以发现\(f\)也是个积性函数，有\(f(p)=1-p,f(p^c)=1-p\)

因为只有次数小于等于\(1\)的质因子会有贡献，所以我们在爆搜枚举因数的时候，如果\(p\nmid i\)，那么\(f(i\times p)=f(i)\times(1-p)\)

然后就没有然后了

//minamoto#include
    
     #define R register#define fp(i,a,b) for(R int i=a,I=b+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}char sr[1<<21],z[20];int C=-1,Z=0;inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}void print(R int x){    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++C]=z[Z],--Z);sr[++C]='\n';}const int N=1e5+5,P=1e9+7,inv2=500000004;inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}int ksm(R int x,R int y){    R int res=1;    for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);    return res;}bitset
      
       vis;int p[N],v[N],c[N],top,m,sqr,n,tot,res,g;void init(int n){    fp(i,2,n){        if(!vis[i])p[++tot]=i;        for(R int j=1;j<=tot&&1ll*i*p[j]<=n;++j){            vis[i*p[j]]=1;            if(i%p[j]==0)break;        }    }}inline int calc(R int x,R int y){    R int a=n/x,b=(m+x-1)/x;    return 1ll*(a+b)*(a-b+1)%P*y%P;}void dfs(int pos,int val,int mu){    if(pos==top+1)return res=add(res,calc(val,mu)),void();    dfs(pos+1,val,mu),mu=mul(mu,dec(1,v[pos]));    fp(i,1,c[pos])val*=v[pos],dfs(pos+1,val,mu);}void solve(){    top=0,res=0,g=n;    for(R int i=1;i<=tot&&1ll*p[i]*p[i]<=g;++i)if(g%p[i]==0){        v[++top]=p[i],c[top]=0;        while(g%p[i]==0)g/=p[i],++c[top];    }    if(g!=1)v[++top]=g,c[top]=1;    dfs(1,1,1);    res=1ll*res*n%P*inv2%P;    print(res);}int main(){//  freopen("testdata.in","r",stdin);//  freopen("testdata.out","w",stdout);    int T=read();init(sqr=N-5);    while(T--)m=read(),n=read(),solve();    return Ot(),0;}