BZOJ 3930: [CQOI2015]选数 莫比乌斯反演

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 #define LL long long
 8 const LL maxn=100010;
 9 const LL p=(int)1e9+7;
10 LL n,k,l,r;
11 LL ans[maxn]={};
12 LL mpow(LL x,LL y){
13     LL z=1;
14     while(y){
15         if(y&1)z=(z*x)%p;
16         x=(x*x)%p;
17         y>>=1;
18     }
19     return z;
20 }
21 int main(){
22     scanf("%lld%lld%lld%lld",&n,&k,&l,&r);
23     LL a=r/k,b=l/k;if(l%k)++b;
24     for(LL i=r-l;i>=1;--i){
25         LL ww=a/i-b/i; if(b%i==0)++ww;
26         if(ww<=0)continue;
27         ans[i]=(mpow(ww,n)-(ww%p)+p)%p;
28         for(int j=2*i;j<=r-l;j+=i)ans[i]=(ans[i]-ans[j]+p)%p;
29     }
30     if(b==1)ans[1]=(ans[1]+1)%p;
31     printf("%lld\n",ans[1]);
32     return 0;
33 }