传送门

颓了一小时柿子orz

首先题目要求的是$$\sum_{x_1=l}^{{r}\sum_{x_2=l}}{r}...\sum_{x_n=l}^{r}[gcd(x_1,x_2...x_n)=k]$$

显然可以除掉一个k,设\(x=\lceil\frac{l}{k}\rceil,y=\lfloor\frac{l}{k}\rfloor\)即$$\sum_{x_1=x}^{{y}\sum_{x_2=x}}{y}...\sum_{x_n=x}^{y}[gcd(x_1,x_2...x_n)=1]$$

可以联系两个数的情况,也就是$$\begin{matrix} \sum_{i=1}^{{n}\sum_{j=1}}{m}[gcd(i,j)=1] &= \sum_{i=1}^{{n}\sum_{j=1}}{m}\sum_{d|i,d|j}\mu(d)\ &=\sum_{d=1}^{min(n,m)}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor \end{matrix}$$

这里有n个数也是类似的,即$$\sum_{d=1}^{{y}\mu(d)(\lfloor\frac{y}{d}\rfloor-\lfloor\frac{x-1}{d}\rfloor)}n$$

注意后半部分,我们要求的是区间\([x,y]\)的d的倍数个数,也就是两个前缀和的差

然后数论分块即可.注意数据范围,\(\mu\)的前缀和要用杜教筛求

#include<bits/stdc++.h>

#define LL long long

#define db double

#define il inline

#define re register

using namespace std;

const int N=1e6+10,mod=1e9+7;

il int rd()

{

    int x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

il int fpow(int a,int b){int an=1;while(b){if(b&1) an=1ll*an*a%mod;a=1ll*a*a%mod,b>>=1;} return an;}

int n,kk,l,r;

int prm[N],mu[N],mu2[N],pp[N],tt,ans;

bool v[N];

il int gmu(int x)

{

	if(x<=N-10) return mu[x];

	if(v[x/10000]) return mu2[x/10000];

	v[x/10000]=1;

	LL an=1;

	for(int i=2,j;i<=x;i=j+1)

	{

		j=(x/(x/i));

		an-=1ll*gmu(x/i)*(j-i+1);

	}

	return mu2[x/10000]=an;

}

int main()

{

	n=rd(),kk=rd(),l=rd(),r=rd();

	l=(l+kk-1)/kk-1,r/=kk;

	mu[1]=1;

	for(int i=2;i<=N-10;++i)

	{

		if(!pp[i]) pp[i]=1,mu[i]=-1,prm[++tt]=i;

		for(int j=1;j<=tt&&i*prm[j]<=N-10;++j)

		{

			pp[i*prm[j]]=1,mu[i*prm[j]]=-mu[i];

			if(i%prm[j]==0) {mu[i*prm[j]]=0;break;}

		}

	}

	for(int i=2;i<=N-10;++i) mu[i]+=mu[i-1];

	for(int i=1,j=1;i<=r;++j,i=j)

	{

		j=min(l>=i?l/(l/i):(int)1e9,r/(r/i));

		ans=((ans+1ll*(gmu(j)-gmu(i-1))*fpow(r/i-l/i,n)%mod)%mod+mod)%mod;

	}

	printf("%d\n",ans);

    return 0;

}