51Nod 1180. 方格射击游戏[互质对计数](莫比乌斯反演)

日付: 10月 20, 2018

[方格射击游戏 - 51Nod](https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1180)

## Problem
$m \times n$的方格，问从$(1,1)$出发至少需要多少条射线可以覆盖所有其他的点。

数据范围：$1 \le m, n \le 5 \times 10^6$

## Solution
首先需要注意边界情况，当$n=m=1$时答案是0，当只有一行或一列时答案是1。

对于$n, m \ge 2$的情况，同行和同列的点可以用两条射线覆盖，关键是其他的点如何处理。首先坐标变换一下，把$(1,1)$移动到$(0,0)$，$n$和$m$各自减小1，那么现在需要覆盖的点是坐标满足$1 \le i \le n, 1 \le j \le m$的所有点。考察一个点$(i,j)$，如果$gcd(i,j)>1$，那么经过该点的射线也一定经过$(\frac{i}{gcd(i,j)}, \frac{j}{gcd(i,j)})$，因此不对答案做贡献。问题转化为求互质对的数量。这个问题是个经典的莫比乌斯反演。

### Mobius Inversion(莫比乌斯反演)
莫比乌斯反演有两种一般形式，分别是对$n$的约数和倍数枚举
$$f(n) = \sum_{d | n} g(d) \implies g(n) = \sum_{d | n} \mu(d) f(\frac{n}{d})$$
$$f(n) = \sum_{n | d} g(d) \implies g(n) = \sum_{n | d} \mu(\frac{d}{n}) f(d)$$

其中，莫比乌斯函数$\mu$定义如下
$$\mu(n) = 
\begin{cases}
1 \quad n = 1 \\
(-1)^k \quad n = p_1 p_2 \cdots p_k \\
0 \quad else 
\end{cases}
$$
$\mu$是积性函数，可以用欧拉筛法计算

反演的意义在于：直接计算函数$g$很困难，而由上述的方式求和后得到的函数$f$计算比较方便的情况下，可以把$g$表示成$f$的和简化计算。

对于本题，采用第二种形式。记$g(x)$为“$gcd(i,j) = x$的点数”，我们需要求$g(1)$。另记$f(x)$为“$x | gcd(i,j)$的点数”，显然$f(x) = \sum_{x | d} g(d)$，反演得$g(x) = \sum_{x | d} \mu(\frac{d}{x}) f(d) \to g(1) = \sum_d \mu(d)f(d)$。而$f$函数是很容易计算的，$f(x) = \lfloor \frac{m}{x} \rfloor \times  \lfloor \frac{n}{x} \rfloor$。当$x > min(m, n)$时，$f(x)=0$，因此只需枚举到$min(m, n)$即可。

## Code
```c++
#include <bits/stdc++.h>
using namespace std;

// Mu[1] = 1, if x = p1p2...pk, Mu[x] = (-1)^k, else 0
vector<int> mu_n(int n) {
    vector<int> Mu(n), L(n), P;
    Mu[1] = L[1] = 1;
    for (int x = 2; x < n; x++) {
        if (!L[x]) P.push_back(L[x] = x), Mu[x] = -1;
        for (auto p : P) {
            if (x * p >= n) break;
            L[x * p] = p;
            if (x % p == 0) { Mu[x * p] = 0; break; }
            else Mu[x * p] = -Mu[x];
        }
    }
    return Mu;
}

// 51Nod. 1180
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    if (n > m) swap(n, m);
    m--, n--;
    if (n == 0) return !printf(!m ? "0\n" : "1\n");
    auto Mu = mu_n(n + 1);
    auto tot = 0LL;
    for (int i = 1; i <= n; i++) {
        tot += 1LL * Mu[i] * (n / i) * (m / i);
    }
    cout << tot + 2 << endl;
    return 0;
}
```

KONGROOの基地

このブログを検索

51Nod 1180. 方格射击游戏[互质对计数](莫比乌斯反演)

コメント

コメントを投稿