bzoj 3930: [CQOI2015]選數 莫比烏斯反演+杜教篩

題意

我們知道，從區間[L,H]（L和H為整數）中選取N個整數，總共有(H-L+1)^N種方案。小z很好奇這樣選出的數的最大公約數的規律，他決定對每種方案選出的N個整數都求一次最大公約數，以便進一步研究。然而他很快發現工作量太大了，于是向你尋求幫助。你的任務很簡單，小z會告訴你一個整數K，你需要回答他最大公約數剛好為K的選取方案有多少個。由于方案數較大，你隻需要輸出其除以1000000007的餘數即可。

1≤N,K≤10^9，1≤L≤H≤10^9，H-L≤10^5

分析

顯然按照一般套路就是設 f(d) 表示 gcd==d 的方案數， g(d) 表示 d|gcd 的方案數。

容易得到 g(d)=(⌊Hd⌋−⌊L−1d⌋)n 還有

f(d)=∑d|kg(k)μ(kd)=∑i=1⌊Hd⌋μ(i)g(di)

f(d)=∑i=1⌊Hd⌋μ(i)(⌊Hdi⌋−⌊L−1di⌋)

看到下取整就知道可以分塊啦。

處理 μ 的字首和的話，小的預處理，大的杜教篩即可。

據說有一種超水的dp做法，但是懶得學啦。

代碼

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;

typedef long long LL;

const int N=;
const int inf=;
const int MOD=;

int tot,n,k,l,r,prime[N/],mu[N];
bool not_prime[N];
map<int,int> w;

void prework(int n)
{
    mu[]=;
    for (int i=;i<=n;i++)
    {
        if (!not_prime[i]) prime[++tot]=i,mu[i]=-;
        for (int j=;j<=tot&&i*prime[j]<=n;j++)
        {
            not_prime[i*prime[j]]=;
            if (i%prime[j]==)
            {
                mu[i*prime[j]]=;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
    for (int i=;i<=n;i++) mu[i]+=mu[i-];
}

int ksm(int x,int y)
{
    int ans=;
    while (y)
    {
        if (y&) ans=(LL)ans*x%MOD;
        x=(LL)x*x%MOD;y>>=;
    }
    return ans;
}

int get_mu(int n)
{
    if (n<=) return mu[n];
    if (w[n]) return w[n];
    int ans=;
    for (int i=,last;i<=n;i=last+)
    {
        last=n/(n/i);
        ans=(ans-(LL)(last-i+)*get_mu(n/i)%MOD)%MOD;;
    }
    return w[n]=ans;
}

int solve()
{
    int ans=;l--;
    for (int i=,last;i<=r;i=last+)
    {
        last=min(l/i?l/(l/i):inf,r/(r/i));
        ans=(ans+(LL)(get_mu(last)-get_mu(i-))*ksm(r/(k*i)-l/(k*i),n)%MOD)%MOD;
    }
    return (ans+MOD)%MOD;
}

int main()
{
    scanf("%d%d%d%d",&n,&k,&l,&r);
    prework();
    printf("%d",solve());
}