ProblemLuogu P3455 (BZOJ1101)ZAP-Queries (莫比乌斯反演+整除分块入门)

Luogu P3455 (BZOJ1101)ZAP-Queries (莫比乌斯反演+整除分块入门)

题目链接:传送门

Description

对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d。
数据组数<=50000, a, b <= 50000

Sample Input

2
4 5 2
6 4 3

Sample Output

3
2

Solution

第一道这种数论题
我们假设n<=m,则有

\sum_{i=1}^n \sum_{j=1}^m [gcd(i, j) == d]

=sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor } [gcd(i, j) == 1]

=\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\sum_{g|i, j}^n \mu(g)

=\sum_{g=1}^n \mu(g) \lfloor \frac{n}{dg} \rfloor \lfloor \frac{m}{dg} \rfloor

然后就能将μ求个前缀和,然后用整除分块来做了
整除分块就是我们可以发现像\lfloor \frac{n}{i}\rfloor这样的式子的取值只有\sqrt N种,而某一段连续的i的区间对应的是同一个值。
我们考虑,如果某一段区间的左端点为d的话,那么所对应的值x就等于\lfloor \frac{n}{d}\rfloor。而区间的右端点的位置显然为\lfloor \frac{n}{x}\rfloor,代入得到此时d = \lfloor \frac{n}{\lfloor \frac{n}{d}\rfloor}\rfloor
于是就这样处理即可,复杂度为O(\sqrt N)

Code

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int Maxn = 100000;

int N, M, D;
int Not_Prime[Maxn + 100], Prime[Maxn + 100], Mu[Maxn + 100], cnt;

inline void Init()
{
    Not_Prime[0] = Not_Prime[1] = 1;
    Mu[1] = 1;
    for (int i = 2; i <= Maxn; ++i)
    {
        if (!Not_Prime[i])
        {
            Prime[++cnt] = i;
            Mu[i] = -1;
        }
        for (int j = 1; j <= cnt && i  * Prime[j] <= Maxn; ++j)
        {
            Not_Prime[i * Prime[j]] = 1;
            if (!(i % Prime[j])) break;
            Mu[i * Prime[j]] = -Mu[i];
        }
    }
    for (int i = 2; i < Maxn; ++i)
        Mu[i] += Mu[i - 1];
}

inline LL Solve ()
{
    N /= D;
    M /= D;
    int last;
    if (N > M) swap(N, M);
    LL Ans = 0ll;
    for (int i = 1; i <= N; i = last + 1)
    {
        last = min(N / (N / i), M / (M / i));
        Ans += 1LL * (Mu[last] - Mu[i - 1]) * (N / i) * (M / i);
    }
    return Ans;
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    int T;
    scanf("%d", &T);
    Init();
    while (T--)
    {
        scanf("%d%d%d", &N, &M, &D);
        printf("%lld\n", Solve());
    }
    return 0;
}

Categories: Problem Tags: , , ,

Comments

No Comments Yet. Be the first?

Post a comment