BZOJ1101:[POI2007]Zap 题解

主要思路

这道题是一道很好的题,包含了数论里面的很多技巧。

首先,这是一道多组询问的题,询问数量非常的大,遂放弃使用欧拉函数来求。考虑可以使用莫比乌斯函数的性质来搞,开始从这方面分析。

复习一下莫比乌斯函数的定义:

\[ \mu(x) = \begin{cases} 0, 在x中存在指数大于一的质因子 \\ 1, 在x中质因子指数都为1且质因子个数为偶数 \\ -1, 在x中质因子质数都为1且质因子个数为奇数 \end{cases} \]

我们观察一下答案式子:\(\sum_{i,j} [gcd(x,y)=d]\)。我们先把\(gcd\)部分进行变换:

\[gcd(\frac{x}{d}, \frac{y}{d}) = 1\]

显然,这样的对数为\( \lfloor \frac{x}{d} \rfloor*\lfloor \frac{y}{d} \rfloor \)。我们考虑容斥:因为如果暴力累加的话,会多出很多不该存在的部分,比如说又是2的倍数又是3的倍数的部分。

所以最后答案式为:

\[\sum_{i=1}^{min\{a,b\}} \mu(i)*\lfloor \frac{x}{i} \rfloor*\lfloor \frac{y}{i} \rfloor \]

这时有个技巧,我们可以证明在整数段\([x, min\{ \lfloor \frac{a}{\lfloor \frac{a}{x} \rfloor} \rfloor, \lfloor \frac{b}{\lfloor \frac{b}{x} \rfloor} \rfloor \} ]\)上,\(\lfloor \frac{x}{i} \rfloor*\lfloor \frac{y}{i} \rfloor\)的结果是一样的,直接前缀和与之相乘即可。最后这样的段最坏情况为\(O(\sqrt{a}+\sqrt{b})\),所以时间复杂度比较低。

代码

// BZ1101.cpp
#include <bits/stdc++.h>
#define ll int
using namespace std;
const int MAX_N = 5e4 + 200;
ll mobi[MAX_N], sum[MAX_N], n;
bool vis[MAX_N];
int main()
{
    for (int i = 1; i < MAX_N; i++)
        mobi[i] = 1;
    for (int i = 2; i < MAX_N; i++)
    {
        if (vis[i])
            continue;
        mobi[i] = -1;
        for (int j = 2; i * j < MAX_N; j++)
        {
            vis[i * j] = true;
            if (j % i == 0)
                mobi[i * j] = 0;
            else
                mobi[i * j] *= -1;
        }
    }
    for (int i = 1; i < MAX_N; i++)
        sum[i] = sum[i - 1] + mobi[i];
    scanf("%d", &n);
    while (n--)
    {
        int a, b, k, gx;
        scanf("%d%d%d", &a, &b, &k);
        a /= k, b /= k;
        int ans = 0;
        for (int i = 1; i <= min(a, b); i = gx + 1)
        {
            gx = min(a / (a / i), b / (b / i));
            ans += (sum[gx] - sum[i - 1]) * (a / i) * (b / i);
        }
        printf("%d\n", ans);
    }
    return 0;
}

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注