C++(clang++ 11.0.1) 解法, 执行用时: 4ms, 内存消耗: 512K, 提交时间: 2023-06-27 10:21:45

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6,M=1e9+7;
using ll=long long;
int n,K,L,R,F[N],ans;
int qp(ll a,int x=M-2){
    int res=1;for(;x;x>>=1,a=a*a%M)
        if(x&1)res=a*res%M;return res;
}
int main(){
    ios::sync_with_stdio(false);
    int i,j,k,l,r,x,y;
    cin>>n>>K>>L>>R;
    L=(L-1)/K+1,R=R/K;
    k=max(R-L+1,L);
    for(i=R-L;i;--i){
        l=(L-1)/i+1,r=R/i;
        if(l<=r)F[i]=qp(r-l+1,n);
        for(j=(R-L)/i;j>1;--j)
            (F[i]-=F[i*j])<0&&(F[i]+=M);
        k<=R&&(F[i]-=R/i-(k-1)/i)<0&&(F[i]+=M);
    }
    ans=F[1];
    printf("%d\n",ans);
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 29ms, 内存消耗: 1376K, 提交时间: 2019-08-30 16:30:05

#include<bits/stdc++.h>
#include<tr1/unordered_map>
typedef long long ll;
using namespace std;
const int maxn=1000000+10;
const int mod=1000000007;
ll f[maxn];
ll ksm(ll a,ll n)
{
    ll res=1;
    while(n)
    {
        if(n&1) res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}
int main()
{
	int n,k,L,R;
    scanf("%d%d%d%d",&n,&k,&L,&R);
    for(ll i=R-L;i>=1;i--)
    {
    	ll l=(L-1)/(k*i),r=R/(k*i);
    	f[i]=ksm(r-l,n)-(r-l);
    	for(ll j=2;i*j<(R-L);j++)
    		f[i]=(f[i]-f[i*j]+mod)%mod;
	}
	if(k>=L&&k<=R)	f[1]++;
	printf("%lld\n",f[1]);
    return 0;
}