bzoj 3930: [CQOI2015]選數

題意：

在[L,H]中選n個可重複，有序的數，使這些數的gcd=k。

題解：

1A了很爽。

莫比烏斯反演+杜教篩。

先轉化題意，設 lk=⌊l−1k⌋+1   rk=⌊rk⌋

相當于在[lk,rk]中選n個互質的數。

即 ans=∑a1lk rk∑a2lk rk……∑a1lk rk[gcd(a1,a2，……,an)=1]

反演一波就得到 ans=∑irkμ(i)∗(⌊rki⌋−⌊lk−1i⌋)n

然後杜教篩求 μ 的字首和就可以了。杜教篩

code:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<map>
#include<algorithm>
#include<iostream>
#define LL long long
using namespace std;
LL mu[],prime[];
bool v[];
map<int,LL> sum;
int n,k,l,r,pr;
const LL mod=;
void pre()
{
    memset(v,true,sizeof(v));
    pr=;mu[]=;
    for(int i=;i<=;i++)
    {
        if(v[i]) prime[++pr]=(LL)i,mu[i]=(LL)(-);
        for(int j=;j<=pr&&(LL)i*prime[j]<=;j++)
        {
            v[i*prime[j]]=false;
            if(i%prime[j]==){mu[i*prime[j]]=;break;}
            mu[i*prime[j]]=-mu[i];
        }
    }
    mu[]=;
    for(int i=;i<=;i++) mu[i]=(mu[i]+mu[i-])%mod;
}
LL solve(int n)
{
    if(n<=) return mu[n];
    if(sum[n]) return sum[n];
    LL ans=L;int j;
    for(int i=;i<=n;i=j+)
    {
        j=n/(n/i);
        ans=(ans-solve(n/i)*(j-i+))%mod;
    }
    sum[n]=ans;
    return ans;
}
LL work(LL a,int b)
{
    LL ans=L;
    while(b)
    {
        if(b&) ans=ans*a%mod;
        a=a*a%mod;b>>=;
    }
    return ans;
}
int main()
{
    pre();sum.clear();
    scanf("%d %d %d %d",&n,&k,&l,&r);
    l=(l-)/k+;r/=k;//l=max(l,1);r=max(r,1);
    LL ans=L;int j;
    for(int i=;i<=r;i=j+)
    {
        //ans=(ans+mu[i]*work((r/i-(l-1)/i),n))%mod;
        //printf("%d %lld\n",i,ans);
        j=r/(r/i);
        if((l-)/i) j=min(j,(l-)/((l-)/i));
        ans=(ans+(solve(j)-solve(i-))*work((r/i-(l-)/i),n))%mod;
    }
    printf("%lld",(ans+mod)%mod);
}