求 $\sum_{i=L}^{R}\sum_{i'=L}^{R}....[gcd_{i=1}^{n}(i)==k]$

 

$\Rightarrow \sum_{i=\frac{L}{k}}^{\frac{R}{k}}\sum_{i'=\frac{L}{k}}^{\frac{R}{k}}....[gcd_{i=1}^{n}(i)==1]$

 

$\Rightarrow \sum_{i=\frac{L}{k}}^{\frac{R}{k}}\sum_{i'=\frac{L}{k}}^{\frac{R}{k}}....\sum_{d|gcd_{i=1}^{n}(i)}\mu(d)$

 

$\Rightarrow\sum_{d=1}^{\frac{R}{d}}\mu(d)(\left \lfloor \frac{R}{kd} \right \rfloor-\left \lfloor \frac{L-1}{kd} \right \rfloor)^n$

 

用杜教筛算莫比乌斯函数前缀和，整除分块算一下就行.

#include<bits/stdc++.h>

#define maxn 1040000

#define M 1000001

#define inf 0x7f7f7f7f

#define ll long long

using namespace std;

ll mod = 1000000007;

void setIO(string s)

{

	string in=s+".in";

	freopen(in.c_str(),"r",stdin);

}

map<int,ll>ansmu;

int cnt;

bool vis[maxn];

int prime[maxn], mu[maxn];

ll sumv[maxn];

ll qpow(ll base,ll k)

{

	ll tmp=1;

	while(k)

	{

		if(k&1) tmp=tmp*base%mod;

		base=base*base%mod;

		k>>=1;

	}

	return tmp;

}

void Linear_shaker()

{

	mu[1]=1;

	int i,j;

	for(i=2;i<=M;++i)

	{

		if(!vis[i]) prime[++cnt]=i, mu[i]=-1;

		for(j=1;j<=cnt&&1ll*i*prime[j]<=M;++j)

		{

			vis[i*prime[j]]=1;

			if(i%prime[j]==0)

			{

				mu[i*prime[j]]=0;

				break;

			}

			mu[i*prime[j]]=-mu[i];

		}

	}

	for(i=1;i<=M;++i) sumv[i]=(sumv[i-1]+mu[i]+mod)%mod;

}

ll get(ll n)

{

	if(n<=M) return sumv[n];

	if(ansmu[n]) return ansmu[n];

	ll i,j,re=0;

	for(i=2;i<=n;i=j+1)

	{

		j=(n/(n/i));

		re=(re+(j-i+1)%mod*get(n/i)%mod+mod)%mod;

	}

	return ansmu[n]=(1ll-re+mod)%mod;

}

int main()

{

	// setIO("input");

	ll n,k,L,R,i,j,re=0;

	scanf("%lld%lld%lld%lld",&n,&k,&L,&R);

	L = (L - 1) / k, R = R / k;

	Linear_shaker();

	for(i=1;i<=R;i=j+1)

	{

		j=min(R/(R/i), L/i?L/(L/i):inf);

		re=(re+qpow(R/i-L/i, n) * (get(j)-get(i-1)+mod)%mod)%mod;

	}

	printf("%lld\n",re);

	return 0;

}