正题
题目大意
在 [L,R] 选n个数,问gcd=k的方案数
解题思路
因为gcd=k,那么所选的数都是k的倍数,那么可以让L,R整除k,那么有
∑ a 1 = L R ∑ a 2 = L R . . . ∑ a n = L R [ g c d ( a 1 , a 2 . . . a n ) = 1 ] \sum_{a_1=L}^R\sum_{a_2=L}^R...\sum_{a_n=L}^R[gcd(a_1,a_2...a_n)=1] a1=L∑Ra2=L∑R...an=L∑R[gcd(a1,a2...an)=1]
∑ a 1 = l r ∑ a 2 = l r . . . ∑ a n = l r ∑ d ∣ a 1 , d ∣ a 2 . . . d ∣ a n μ ( d ) \sum_{a_1=l}^r\sum_{a_2=l}^r...\sum_{a_n=l}^r\sum_{d|a_1,d|a_2...d|a_n}\mu(d) a1=l∑ra2=l∑r...an=l∑rd∣a1,d∣a2...d∣an∑μ(d)
∑ d = 1 n μ ( d ) ( r d − l − 1 d ) n \sum_{d=1}^n\mu(d)(\frac{r}{d}- \frac{l-1}{d})^n d=1∑nμ(d)(dr−dl−1)n
然后可以整除分块, μ \mu μ 用杜教筛求
code
#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 2000210
#define mod 1000000007
using namespace std;
ll n,k,L,R,w,ans,mu[N],p[N],prime[N];
map<ll,ll>smu;
const ll MX=2e6;
void work()
{
mu[1]=1;
for(ll i=2;i<=MX;++i){
if(!p[i]){
mu[i]=-1;
prime[++w]=i;
}
for(ll j=1;j<=w&&i*prime[j]<=MX;++j){
p[i*prime[j]]=1;
if(i%prime[j]==0)break;
mu[i*prime[j]]=-mu[i];
}
}
for(ll i=2;i<=MX;++i)
mu[i]+=mu[i-1];
return;
}
ll S(ll n)
{
if(n<=MX)return mu[n];
if(smu.find(n)!=smu.end())return smu[n];
ll g=1;
for(ll l=2,r;l<=n;l=r+1){
r=n/(n/l);
g-=S(n/l)*(r-l+1);
}
smu[n]=g;
return g;
}
ll ksm(ll x,ll y)
{
ll z=1;
while(y){
if(y&1)z=z*x%mod;
x=x*x%mod;
y>>=1;
}
return z;
}
int main()
{
work();
scanf("%lld%lld%lld%lld",&n,&k,&L,&R);
L=(L+k-1)/k-1;
R/=k;
for(ll l=1,r;l<=R;l=r+1){
if(L/l)r=min(L/(L/l),R/(R/l));
else r=R/(R/l);
(ans+=(S(r)-S(l-1))*ksm(R/l-L/l,n)%mod+mod)%=mod;
}
printf("%lld",ans);
return 0;
}