[CQOI2015] 选数

ganking / 2023-08-23 / 原文

[CQOI2015] 选数
开始感觉挺不好搞的，值域很大，但是发现除了全部相等的情况，gcd的取值只有1e5级别，所以最后特判全部相等的情况即可。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<unordered_map>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
using namespace std;
typedef long long ll;
const ll mo=1e9+7;
const int N=1e5+5;
ll n,k,l,r,z,x,y,ans;
ll f[N];
ll power(ll a,ll b){
	ll t=1,y=a%mo;
	while (b){
		if (b&1) t=t*y%mo;
		y=y*y%mo;
		b/=2;
	}
	return t;
}
void add(ll &x,ll y){
	x=(x+y)%mo;
}
int main() {
   
//	freopen("data.in","r",stdin);
//  	freopen("data.out","w",stdout);
   	

   	scanf("%lld %lld %lld %lld",&n,&k,&l,&r);
   	if (l%k==0) l/=k; else l=l/k+1;
   	r/=k;
	
	if (l>r) {
		printf("%d",0);
		return 0;
	}
	
	fo(i,1,r-l) {
		if (l%i==0) x=l/i; else x=l/i+1;
		y=r/i;
		if (x>y) continue;
		
		f[i]=(power(y-x+1, n)-(y-x+1) )%mo;
	}
	fd(i,r-l,1) {
		fo(j,2,(r-l)/i) {
			f[i]=(f[i]- f[i*j])%mo;
		}
	}
	ans=f[1];
	if (l==1) ans++;
	
	ans=(ans%mo+mo)%mo;
	printf("%lld",ans);

    return 0;
}