P3172 [CQOI2015]选数（莫比乌斯反演+杜教筛）

P3172 [CQOI2015]选数

题意

给定区间[L,H]，区间内n个数的最大公约数为k的方案书有多少个。即求
$$\sum _{a_1=L}^H\sum _{a_2=L}^H...\sum _{a_n=L}^H[gcd(a_1,a_2,...,a_n)=k]$$

Solution

$$\begin{gathered} \sum _{a_1=L}^H\sum _{a_2=L}^H...\sum _{a_n=L}^H[gcd(a_1,a_2,...,a_n)=k] \\ =\sum _{a_1=L}^H\sum _{a_2=L}^H...\sum _{a_n=L}^H[gcd(\frac{a_1}{k},\frac{a_2}{k},...,\frac{a_n}{k})=1] \\ =\sum _{a_1=\lceil \frac{L}{k}\rceil }^{\lfloor \frac{H}{k}\rfloor }\sum _{a_2=\lceil \frac{L}{k}\rceil }^{\lfloor \frac{H}{k}\rfloor }...\sum _{a_n=\lceil \frac{L}{k}\rceil }^{\lfloor \frac{H}{k}\rfloor }[gcd(a_1,a_2,...,a_n)=1] \\ =\sum _{a_1=\lceil \frac{L}{k}\rceil }^{\lfloor \frac{H}{k}\rfloor }\sum _{a_2=\lceil \frac{L}{k}\rceil }^{\lfloor \frac{H}{k}\rfloor }...\sum _{a_n=\lceil \frac{L}{k}\rceil }^{\lfloor \frac{H}{k}\rfloor }\sum _{d|gcd(a_1,a_2,...,a_n)}\mu (d) \\ =\sum _{d=1}^{\lfloor \frac{H}{k}\rfloor }\mu (d)\sum _{a_1=\lceil \frac{L}{dk}\rceil }^{\lfloor \frac{H}{dk}\rfloor }\sum _{a_2=\lceil \frac{L}{dk}\rceil }^{\lfloor \frac{H}{dk}\rfloor }...\sum _{a_n=\lceil \frac{L}{dk}\rceil }^{\lfloor \frac{H}{dk}\rfloor }1 \\ =\sum _{d=1}^{\lfloor \frac{H}{k}\rfloor }\mu (d)(\lfloor \frac{H}{dk}\rfloor -\lfloor \frac{L-1}{dk}\rfloor {)}^n \end{gathered}$$

杜教筛求前缀和：

$$\begin{gathered} S(n)=\sum _{i=1}^{n}f(i) \\ \sum _{i=1}^n(f\ast g)(i)=\sum _{i=1}^n\sum _{d|i}g(d)\ast f(\frac{i}{d}) \\ =\sum _{d=1}^n\sum _{d|i}g(d)\ast f(\frac{i}{d}) \\ =\sum _{d=1}^{n}g(d)\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }f(i) \\ =\sum _{d=1}^{n}g(d)S(\lfloor \frac{n}{d}\rfloor ) \\ 根据积性函数g(1)=1 \\ S(n)=\sum _{i=1}^n(f\ast g)(i)-\sum _{d=2}^{n}g(d)S(\lfloor \frac{n}{d}\rfloor ) \end{gathered}$$
记$n=\lfloor \frac{H}{k}\rfloor$，那么
$$\begin{gathered} S(n)=\sum _{i=1}^{\lfloor \frac{H}{k}\rfloor }\mu (i)=\sum _{i=1}^n\mu (i) \\ 根据\mu \ast 1=e,S(n)=\sum _{i=1}^{n}e(i)-\sum _{d=2}^{n}g(d)S(\lfloor \frac{n}{d}\rfloor ) \\ =1-\sum _{d=2}^{n}S(\lfloor \frac{n}{d}\rfloor ) \end{gathered}$$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
unordered_map<ll,ll>mpsu;
const int mod=1e9+7;
const int N=1e6;
int prime[N+5],notprime[N+5],cnt=0;
int mu[N+5],smu[N+5];
void initMu()
{
   
    mu[1]=1;
    for(int i=2;i<=N;i++)
    {
   
        if(!notprime[i])
        {
   
            mu[i]=-1;
            prime[cnt++]=i;
        }
        for(int j=0;j<cnt&&1ll*i*prime[j]<=N;j++)
        {
   
            notprime[i*prime[j]]=1;
            if(i%prime[j])mu[i*prime[j]]=-mu[i];
            else {
   mu[i*prime[j]]=0;break;}
        }
    }
    for(int i=1;i<=N;i++)smu[i]=smu[i-1]+mu[i];
}
ll fpow(ll x,int power)
{
   
    ll ans=1;
    while(power)
    {
   
        if(power&1)ans=ans*x%mod;
        power>>=1;
        x=x*x%mod;
    }
    return ans;
}
ll getSmu(ll x)
{
   
    if(x<=N)return smu[x];
    if(mpsu[x]!=0)return mpsu[x];
    ll ans=1;
    for(int l=2,r;l>=0&&l<=x;l=r+1)
    {
   
        r=x/(x/l);
        ans=(ans-1ll*getSmu(x/l)*(r-l+1)%mod)%mod;
    }

    return mpsu[x]=(ans+mod)%mod;
}
int n,k,L,H;
int main()
{
   
    initMu();
    scanf("%d%d%d%d",&n,&k,&L,&H);
    H=H/k;
    L=(L-1)/k;
    ll res=0;
    for(int l=1,r;l<=H;l=r+1)
    {
   
        if(L>=l)
            r=min(H/(H/l),L/(L/l));
        else
            r=H/(H/l);
        res=(res+1ll*fpow(H/l-L/l,n)*(getSmu(r)-getSmu(l-1))%mod+mod)%mod;
    }
    printf("%lld",res);
    return 0;
}