C++11(clang++ 3.9) 解法, 执行用时: 85ms, 内存消耗: 1316K, 提交时间: 2020-07-11 10:06:01

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k,l,r,i,j,mod=1000000007,ans[100010],s;
ll pow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)
            res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main()
{
    cin>>n>>k>>l>>r;
    for(i=1; i<=r-l+1; i++)
    {
        ll len=r/i-(l-1)/i;
        ans[i]=(pow(len,n)-len+mod)%mod;
    }
    for(i=r-l+1; i>=1; i--)
        for(j=2*i; j<=r-l+1; j+=i)
            ans[i]=(ans[i]-ans[j]+mod)%mod;
    if(r-l+1<=k)
        s=0;
    else
        s=ans[k];
    if(k<=r&&k>=l)
        s++;
    cout<<s<<endl;
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 134ms, 内存消耗: 1272K, 提交时间: 2019-08-28 16:07:58

#include<bits/stdc++.h>
using namespace std;

long long n,m,k,l,r,i,j,mod=1000000007,ans[100010],s;
long long pow(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1)
		{
			res=res*a%mod;	
		}
		a=a*a%mod;
		b/=2;
	}
	return res;
}
int main()
{
	scanf("%lld%lld%lld%lld",&n,&k,&l,&r);
	for(i=1;i<=r-l+1;i++)
	{
		long long len=r/i-(l-1)/i;
		ans[i]=(pow(len,n)-len+mod)%mod;
	}
	for(i=r-l+1;i>=1;i--)
	{
		for(j=2*i;j<=r-l+1;j+=i)
		{
			ans[i]=(ans[i]-ans[j]+mod)%mod;
		}
	}
	if(r-l+1<=k)
	    s=0;
    else
        s=ans[k];
	if(k<=r&&k>=l)s++;
	printf("%lld\n",s);
	return 0;
}

pypy3(pypy3.6.1) 解法, 执行用时: 190ms, 内存消耗: 27504K, 提交时间: 2021-05-10 20:15:32

#!/usr/bin/env python3
#
# NC21546 - 牛牛的最大公约数
#
import sys, os, math, functools

MOD = int(1e9 + 7)

n, k, l, r = map(int, input().split())
s = r - l + 1
a = [0] * (s + 1)
for i in range(1, s + 1):
	d = r // i - (l - 1) // i
	a[i] = (pow(d, n, MOD) - d + MOD) % MOD
for i in range(s, 0, -1):
	for j in range(i * 2, s + 1, i):
		a[i] = (a[i] - a[j] + MOD) % MOD
if k >= s:
	print(1 if l <= k <= r else 0)
else:
	if l <= k <= r: a[k] = (a[k] + 1) % MOD
	print(a[k])