【题解】HAOI2011Problem b

　　第一次接触莫比乌斯反演，总之脑子都快要炸掉了……好难啊！本蒟蒻表示根本无法理解呜呜呜呜呜……不过在机房DL的帮助下总算是磕磕绊绊的A掉了这一题：

　　这道题目要我们的求的是：（1）Σ_iΣ_j [gcd(i,j)==k]，区间范围内的限定我们都可以利用容斥来解决，所以默认为所求函数值的(i, j)取值范围为（1~n,1~m）。注意到gcd(i, j) == k比较的不好求解，我们把k除到外面去，得到：（2）Σ_iΣ_j [gcd(i,j)==1](i∈n/k, j∈m/k); 这里将[gcd(i,j)==1]替换为单位元ε（ε(i) = i == 1 ? 1 : 0）。根据狄利克雷卷积有μ * 1 = ε（*为卷积符号），所以我们得到式子（3）Σ_iΣ_jΣ_d|gcd(i,j)μ(d)。这里是考虑对于每一对i,j有哪几个d与之对应，我们将d提取出来，反之枚举符合d|gcd(i,j)的数对。由此有（4）Σ_dμ(d) * (n / (d*k)) * (m / (d * k))(d∈min(n, m) / (d * k))。

　　但是利用最后这个式子求解的复杂度依然太高了，不过因为n/i的取值最多只有2*sqrt(n)种（若i<sqrt(n)，i的取值只有sqrt(n)种，若i>=sqrt(n)，n/i<=sqrt(n)，所以一共最多只有2*sqrt(n)种），所以在很大的范围内实际上(n / (d*k)) * (m / (d * k))都是一个常数，我们就可以利用μ(d)的前缀和来实现快速求解。

　　设当前枚举到的d，pos = min(n / (n / d), m / (m / d)); 这个pos就是从当前位置一直到达pos，(n / (d*k)) * (m / (d * k))都是一个常数，只需要计算一次之后利用前缀和求解。

　　贴代码，再一次被自己蠢哭，智商堪忧怎么办啊QAQ（向数学组DL低头，伏地%%%，跪地%%%!!!）

#include <bits/stdc++.h>

using namespace std;

#define maxn 65000

int tot, T, maxx = , sum[maxn], pri[maxn], Mu[maxn];

bool is_prime[maxn];

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

int Get_Mu()

{

    Mu[] = ;

    for(int i = ; i <= maxx; i ++)

    {

        if(!is_prime[i]) pri[++ tot] = i, Mu[i] = -;

        for(int j = ; j <= tot; j ++)

        {

            if(i * pri[j] > maxx) break;

            is_prime[i * pri[j]] = true;

            if(!(i % pri[j]))

            {

                Mu[i * pri[j]] = ;

                break;

            }

            else Mu[i * pri[j]] = - Mu[i];

        }

    }

    for(int i = ; i <= maxx; i ++)

        sum[i] = sum[i - ] + Mu[i];

}

int cal(int n, int m)

{

    if(n > m) swap(n, m);

    int ans = , pos;

    for(int i = ; i <= n; i = pos + )

    {

        pos = min(n / (n / i), m / (m / i));

        ans += (sum[pos] - sum[i - ]) * (n / i) * (m / i);

    }

    return ans;

}

int main()

{

    Get_Mu();

    T = read();

    while(T --)

    {

        int a = read(), b = read(), c = read(), d = read(), k = read();

        a --, c --;

        a /= k, b /= k, c /= k, d /= k;

        int ans = cal(a, c) + cal(b, d) - cal(a, d) - cal(b, c);

        printf("%d\n", ans);

    }

    return ;

}

巴特西

【题解】HAOI2011Problem b

最新文章

热门文章