bzoj 2301(1101) [HAOI2011]Problem b 莫比乌斯反演+分段优化

Description

对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。

Input

第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k

Output

共n行，每行一个整数表示满足要求的数对(x,y)的个数

Sample Input

2

2 5 1 5 1

1 5 1 5 2

Sample Output

14

3

HINT

100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000

​​​1101​​​有双倍经验的说……

这题算是经典题了吧……之前代码基本就是抄的，根本不懂，

今天终于来补了一下。。

这题要求的其实就是：

∑x=1n∑y=1mgcd(x,y)==K

x和y同除以K，则问题转化为gcd(x/K,y/K)==1，也就是

∑x=1⌊nK⌋∑y=1⌊mK⌋gcd(x,y)==1

经典问题辣！现在终于会辣=v=！

设f(i)表示gcd(a,b)=i，1<=a<=N，1<=b<=M,(a,b)的对数

设F(i)表示i|gcd(a,b)，1<=a<=N，1<=b<=M,(a,b)的对数

那么对于F(n)，显然有：

F(n)=∑n|df(d)F(n)=⌊Nn⌋∗⌊Mn⌋

接下来使用莫比乌斯反演定理，

莫比乌斯反演的证明等等可以百度搜索，具体2种形式如下：

若F(n)=∑d|nf(d)，则f(n)=∑d|nμ(d)∗F(nd)若F(n)=∑n|df(d)，则f(n)=∑n|dμ(dn)∗F(d)

那么这题显然是第二种形式了，我们得到：

f(i)=∑i|dμ(di)∗⌊Ni⌋∗⌊Mi⌋也可以写成f(i)=∑k=1min(N,M)/iμ(k)∗⌊Nki⌋∗⌊Mki⌋

对于下面的式子我们发现，可以O(N)求出答案，

那么总时间复杂度O(TN)，T为数据组数。这题却会TLE。

如何优化呢？对于形如⌊Ni⌋的式子，

我们一般都有一个“分块优化”，因为这个式子的值数只有O(n−√)种，

或者确切一点，2n−√种。

那么也就是说总有一段是一样的，如何算最长的值为一样的一段呢？

答案是⌊NNi⌋，

因为我们知道⌊Ni⌋=x，

x表示的是能够使得⌊Nx⌋=i的最小x，

那么x既然最小，再除一次就变成上界了。

每次在⌊Ni⌋和⌊Mi⌋里面找一个更小的值，

记录为last，那么(i~last)的⌊Ni⌋和⌊Mi⌋都是一样的，只要求出这一段里的μ(x)的和即可，

那么i每次更新为last+1即可，

为了快速求出这一段莫比乌斯函数的和，

之前用个线性筛+前缀和就好了，

这样就优化到了O(Tn−√)

好题啊，经典题！

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int 
    maxn=50005;
int prime[maxn/7],mu[maxn],summu[maxn];
bool notprime[maxn];
void Get_mu(){
    notprime[1]=1,mu[1]=1;
    int pcnt=0;
    for (int i=2;i<maxn;i++){
        if (!notprime[i]) mu[i]=-1,prime[++pcnt]=i;
        for (int j=1;j<=pcnt;j++){
            if (i*prime[j]>=maxn) break;
            notprime[i*prime[j]]=1;
            if (i%prime[j]) mu[i*prime[j]]=-mu[i];
                else{
                    mu[i*prime[j]]=0;
                    break;
                }
        }
    }
    summu[0]=0;
    for (int i=1;i<maxn;i++) summu[i]=summu[i-1]+mu[i];
}
ll calc(int n,int m){
    int tmp=min(n,m),last;
    ll ans=0LL;
    for (int i=1;i<=tmp;i=last+1){
        last=min(n/(n/i),m/(m/i));
        ans+=(ll)(summu[last]-summu[i-1])*(n/i)*(m/i);
    }
    return ans;
}
ll ANS(int a,int b,int c,int d,int K){
    a--,c--;
    a/=K,b/=K,c/=K,d/=K;
    return calc(b,d)-calc(a,d)-calc(b,c)+calc(a,c);
}
int main(){
    Get_mu();
    int cas;scanf("%d",&cas);
    int a,b,c,d,K;
    while (cas--){
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&K);
        printf("%lld\n",ANS(a,b,c,d,K));
    }
    return 0;
}