题解
题解
我是真的不明白这玩意儿是怎么跟反演扯上关系的……
首先
[egin{align}
ans
&=bsum_{d|b}{1over d}sum_{i=a}^{b}i[gcd(i,b)=d]\
&=bsum_{d|b}sum_{i=lceil{aover d}
ceil}^{bover d}i[gcd(i,{bover d})=1]\
end{align}
]
然后有一个非常神仙的操作……就是强行反演一波，把([n=1])化成(sum_{i|n}mu(i))
[egin{align}
ans
&=bsum_{d|b}sum_{i=lceil{aover d}
ceil}^{bover d}isum_{j|gcd(i,{bover d})}mu(j)\
&=bsum_{d|b}sum_{j|{bover d}}mu(j)sum_{i=lceil{aover d}
ceil}^{bover d}[i mod j=0]\
&=bsum_{d|b}sum_{j|{bover d}}mu(j)sum_{i=lceil{aover d}
ceil}^{bover d}[i mod j=0]\
&={bover 2}sum_{d|b}sum_{j|{bover d}}mu(j)j(lfloor{bover {dj}}
floor+lceil{aover {dj}}
ceil)(lfloor{bover {dj}}
floor-lceil{aover {dj}}
ceil+1)\
&={bover 2}sum_{T|b}(lfloor{bover T}
floor+lceil{aover T}
ceil)(lfloor{bover T}
floor-lceil{aover T}
ceil+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 mid i)，那么(f(i imes p)=f(i) imes(1-p))
然后就没有然后了
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(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]='
';
}
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<N>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;
}