神仙题，不需要反演
首先上下界同时除以$k$，转换成取$n$个$gcd$为$1$的数的方案数，其中上界向下取整，下界向上取整
然后设$f[i]$表示选$n$个互不相同的数$gcd$为$i$的方案数，这么设是为了容斥，然后就可以直接求出来$f[i]=m^n-m$，其中m是$i$倍数的个数
同时从大到小容斥就可以了
1 #include<cstdio> 2 #include<vector> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int mod=1e9+7; 7 int n,k,l,r,ln,ans[100005]; 8 int Qpow(int x,int k) 9 { 10 if(k==1) return x; 11 int tmp=Qpow(x,k/2); 12 return k%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod; 13 } 14 int main() 15 { 16 scanf("%d%d%d%d",&n,&k,&l,&r); 17 l=(l+k-1)/k,r/=k,ln=r-l; 18 for(int i=ln;i;i--) 19 { 20 int ll=(l+i-1)/i,rr=r/i,len=rr-ll+1; 21 ans[i]=(Qpow(len,n)-len+mod)%mod; 22 for(int j=i*2;j<=ln;j+=i) 23 ans[i]=(ans[i]-ans[j]+mod)%mod; 24 } 25 printf("%d",ans[1]+(l==1)); 26 return 0; 27 }