题意
给定 \(L,R,N,K\)。选出 \(N\) 个 \([L,R]\) 的整数有 \((R-L+1)^N\) 种选法，问其中多少种的 \(\gcd\) 为 \(K\)。\(N,K,L,R\leq 10^9\)，\(R-L\leq 10^5\)。
题解
若干差不超过 \(10^5\) 的数，其 \(\gcd\) 显然不超过 \(10^5\)。枚举 \(\gcd\)，简单反演得：
\[\sum_{i=1}^n\mu(i)g(i) \]\(g(i)\) 整除一下快速幂即可。
#include<bits/stdc++.h>
using namespace std;
int getint(){
int ans=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9'){
ans=ans*10+c-'0';
c=getchar();
}
return ans;
}
const int N=1e5+10,mod=1000000007;
bool boo[N];
int pri[N],cnt=0,f[N];
int l,r,n;
int qpow(int x,int y){
int ans=1;
while(y){
if(y&1)ans=ans*1ll*x%mod;
x=x*1ll*x%mod;
y>>=1;
}
return ans;
}
int calc(int k){
int p=(l+k-1)/k,q=r/k;
return (qpow(q-p+1,n)-1ll-q+p)%mod;
}
int main(){
n=getint();
int k=getint();
l=getint(),r=getint();
r/=k;
l=(l+k-1)/k;
int m=r-l+1;
f[1]=1;
for(int i=2;i<=m;i++){
if(!boo[i])pri[cnt++]=i,f[i]=-1;
for(int j=0;j<cnt&&i*pri[j]<=m;j++){
boo[i*pri[j]]=1;
if(i%pri[j])f[i*pri[j]]=-f[i];
else break;
}
}
int ans=0;
for(int i=1;i<=m;i++)
ans=(ans+calc(i)*1ll*f[i])%mod;
if(l<=1&&1<=r)ans++;
ans=(ans+mod)%mod;
cout<<ans;
}