题目链接

题解

反演得到

\sum_{i=1}^{\lfloor h/k\rfloor} \mu(i) (\lfloor \frac{h}{ki}\rfloor-\lfloor\frac{l-1}{ki}\rfloor)^n

整除分块直接算即可。

代码

#include #include 
     
      #include 
      
       int read(){
      int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {
          if(ch=='-')        {
              f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {
          x=x*10+ch-'0';      ch=getchar();    }  return x*f;}const int maxn=1000000;const int mod=1000000007;const int inf=0x3f3f3f3f;int p[maxn+10],prime[maxn+10],cnt,mu[maxn+10];int getprime(){
      p[1]=mu[1]=1;  for(int i=2; i<=maxn; ++i)    {
          if(!p[i])        {
              prime[++cnt]=i;          mu[i]=mod-1;        }      for(int j=1; (j<=cnt)&&(i*prime[j]<=maxn); ++j)        {
              int x=i*prime[j];          p[x]=1;          if(i%prime[j]==0)            {
                  mu[x]=0;              break;            }          mu[x]=mod-mu[i];        }    }  for(int i=1; i<=maxn; ++i)    {
          mu[i]+=mu[i-1];      if(mu[i]>=mod)        {
              mu[i]-=mod;        }    }  return 0;}std::map
       
         mp;int getsum(int n){
      if(n<=maxn)    {
          return mu[n];    }  if(mp.count(n))    {
          return mp[n];    }  int ans=1;  for(int l=2,r; l<=n; l=r+1)    {
          r=n/(n/l);      ans-=1ll*(r-l+1)*getsum(n/l)%mod;      if(ans<0)        {
              ans+=mod;        }    }  return mp[n]=ans;}int n,k,s,t;int quickpow(int a,int b){
      int res=1;  while(b)    {
          if(b&1)        {
              res=1ll*res*a%mod;        }      a=1ll*a*a%mod;      b>>=1;    }  return res;}int main(){
      getprime();  n=read();  k=read();  s=read();  t=read();  int ans=0;  for(int l=1,r; l<=t/k; l=r+1)    {
          r=inf;      if(t/(l*k)!=0)        {
              r=std::min(r,t/(t/(l*k)));        }      if((s-1)/(l*k)!=0)        {
              r=std::min(r,(s-1)/((s-1)/(l*k)));        }      r/=k;      ans=(ans+1ll*(getsum(r)-getsum(l-1)+mod)*quickpow((t/(k*l))-((s-1)/(k*l)),n))%mod;    }  printf("%d\n",ans);  return 0;}