大致题意： 让你求出在区间([L,H])间选择(n)个数时，有多少种方案使其(gcd)为(K)。
容斥
原以为是一道可怕的莫比乌斯反演题。
但是，数据范围中有这样一句话：(H-Lle10^5)。
于是，它就变成了一道可以用容斥乱搞的题目。
大致思路
首先，我们将(L)与(H)分别除以(K)（注意(L)向上取整，(H)向下取整，这应该还是比较好理解的）。
然后我们在([1,H-L])之间枚举(i)，假设(x)表示([L,H])区间内选出(i)的倍数的个数，则选择(n)个数使得这些数全部含有约数(i)的方案数应为(x^n-x)。
那么如何求出最大公约数是(i)的方案数呢？
很简单，根据容斥原理，全是(i)倍数的方案数中多余的方案数应为最大公约数为(2i,3i,4i,...)的方案数，所以我们可以倒着求一遍，得出答案。
具体实现详见代码吧。
代码
#include<bits/stdc++.h>
#define MOD 1000000007
#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))
#define Dec(x,y) ((x-=(y))<0&&(x+=MOD))
#define Delta 100000
using namespace std;
int n,k,l,r,f[Delta+5];
inline int quick_pow(int x,int y,register int res=1)//快速幂
{
for(;y;x=1LL*x*x%MOD,y>>=1) if(y&1) res=1LL*res*x%MOD;
return res;
}
int main()
{
register int i,j,x,y;
for(scanf("%d%d%d%d",&n,&k,&l,&r),(l+=k-1)/=k,r/=k,i=1;i<=r-l;++i) x=(l+i-1)/i,y=r/i,f[i]=quick_pow(y-x+1,n),Dec(f[i],y-x+1);//求出含有约数i的方案数f[i]
for(i=r-l;i;--i) for(j=i<<1;j<=r-l;j+=i) Dec(f[i],f[j]);//容斥，求出gcd为i的方案数f[i]
return printf("%d",f[1]+(l==1)),0;//特判l=1的情况，将f加1
}