颓了一小时柿子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=lceilfrac{l}{k} ceil,y=lfloorfrac{l}{k} floor)即$$sum_{x_1=x}{y}sum_{x_2=x}{y}...sum_{x_n=x}^{y}[gcd(x_1,x_2...x_n)=1]$$
可以联系两个数的情况,也就是$$egin{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)lfloorfrac{n}{d} floorlfloorfrac{m}{d} floor end{matrix}$$
这里有n个数也是类似的,即$$sum_{d=1}{y}mu(d)(lfloorfrac{y}{d} floor-lfloorfrac{x-1}{d} floor)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
",ans);
return 0;
}