BZOJ 2301 - 莫比烏斯反演 + 字首和 + 分塊計算

題意：對于給出的 n 個詢問，每次求有多少個數對(x,y)，滿足 a≤x≤b，c≤y≤d ，且gcd (x,y)=k 。

首先用容斥原理将一個詢問拆成4個。然後，一種可行的轉化是求一種可行的轉化是先令 k=1 ，即求 1≤floor(x/k)≤n 且 1≤floor(y/k)≤m 的互質數對 (x,y) 的數量。然後我們考慮用莫比烏斯反演。我們經常使用的一種形式是

f(k)=∑k|dμ(dk)F(d)

是以，我們可以設 f(k) 為範圍内 gcd(x,y)=k 的數對個數（即一個詢問的答案），然後設 F(d) 為範圍内 d|gcd(x,y) 的數對個數。我們會發現 F[d] 是比較好算的：它就是 ⌊nd⌋⌊md⌋ ，其中 n 和m分别是 x 和y的取值範圍。别忘了之前我們已經令 k=1 ，是以我們枚舉的 d 其實就是正整數。如果我們枚舉d的話，在原本 k=1 的時候，每次詢問的時間複雜度就會退化成 O(n) 的，是以我們需要改進。

在1257那道題裡面，我們曾經利用過一個結論： n/d 的值有 O(n‾‾√) 個。這樣，我們就可以枚舉這個商，以每個商為一塊，分塊計算之。這裡，我們繼續利用這個結論。我們設 d 在區間[l,r]上時， F[d]=⌊nd⌋⌊md⌋ 的值不變。為了保險起見，我們把它拆成兩個式子： ⌊nl⌋=⌊nr⌋且⌊ml⌋=⌊mr⌋

然後就是和1257一樣的方法，用整除的性質放縮一下，分别得出 r 關于l的兩個範圍，取較小的那一個就行了。下一次循環的 l′ 就是 r+1 。

// BZOJ 2301

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

 const int N=50000+5;

 #define rep(i,a,b) for (int i=a; i<=b; i++)
 #define dep(i,a,b) for (int i=a; i>=b; i--)
 #define read(x) scanf("%d", &x)
 #define fill(a,x) memset(a, x, sizeof(a))

 /* 篩Mobius函數的過程：
 思想一：一邊計算miu函數，一邊篩質數；
 思想二：每個數隻被其最小的質數篩去
 */
 bool vis[N];
 int miu[N], T, a, b, c, d, k, prime[N], sum[N], s1, s2, s3, s4;
 void get_Mobius() {
    int tot=0;
    miu[1]=1; 
    fill(vis, false);
    rep(i,2,N) {
        if (!vis[i]) { prime[++tot]=i; vis[i]=true; miu[i]=-1; }
        for (int j=1; j<=tot && prime[j]*i<=N; j++) {
            int k=prime[j]*i;
            vis[k]=true;
            if (i%prime[j]==0) { miu[k]=0; break; }
            else miu[k]=-miu[i]; 
        }
    }
    sum[0]=0;
    rep(i,1,N) sum[i]=sum[i-1]+miu[i];
 }

 int query(int n, int m) {
    int last=0, ret=0;
    if (n>m) swap(n, m);
    for (int i=1; i<=n; i=last+1) {
        last=min(n/(n/i), m/(m/i));
        ret+=(n/i)*(m/i)*(sum[last]-sum[i-1]);
    }
    return ret;
 }

int main()
{
    get_Mobius();
    read(T);
    while (T--) {
        read(a); read(b); read(c); read(d); read(k);
        a--; c--;
        int s1=query(b/k, d/k), s4=query(a/k, c/k);
        int s2=query(a/k, d/k), s3=query(c/k, b/k);
        printf("%d\n", s1-s2-s3+s4);
    }

    return 0;
}