[CQOI2015] 选数
开始感觉挺不好搞的，值域很大，但是发现除了全部相等的情况，gcd的取值只有1e5级别，所以最后特判全部相等的情况即可。
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<unordered_map>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
using namespace std;
typedef long long ll;
const ll mo=1e9+7;
const int N=1e5+5;
ll n,k,l,r,z,x,y,ans;
ll f[N];
ll power(ll a,ll b){
ll t=1,y=a%mo;
while (b){
if (b&1) t=t*y%mo;
y=y*y%mo;
b/=2;
}
return t;
}
void add(ll &x,ll y){
x=(x+y)%mo;
}
int main() {
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
scanf("%lld %lld %lld %lld",&n,&k,&l,&r);
if (l%k==0) l/=k; else l=l/k+1;
r/=k;
if (l>r) {
printf("%d",0);
return 0;
}
fo(i,1,r-l) {
if (l%i==0) x=l/i; else x=l/i+1;
y=r/i;
if (x>y) continue;
f[i]=(power(y-x+1, n)-(y-x+1) )%mo;
}
fd(i,r-l,1) {
fo(j,2,(r-l)/i) {
f[i]=(f[i]- f[i*j])%mo;
}
}
ans=f[1];
if (l==1) ans++;
ans=(ans%mo+mo)%mo;
printf("%lld",ans);
return 0;
}