自动搬运

查看原文

来自洛谷，原作者为

	Elegia irony

搬运于2025-08-24 21:59:38，当前版本为作者最后更新于2018-04-11 22:38:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

逆向思考，考虑对于一组 $(R, C)$ 其需要穿过的方格数量 $N$ 。

发现问题在 $\gcd(r,c) = 1$ 时不会中途穿过某个点，故每穿过一条边的时候恰多经过了一个方格。此时穿过方格数有 $n = r + c - 1$ 个。

可以得到一般情况，$N = R + C - \gcd(R, C)$ 。我们要对这一方程的解计数。

注意到此时每一个数两边都必须是 $\gcd(R, C)$ 的因数，方程变为

$$\frac{N}{\gcd(R, C)} = r + c - 1$$

的解。

记 $n = \frac{N}{\gcd{R, C}}$ ，由于此时 $\gcd(r, c) = 1$ ，根据欧几里得算法我们可以知道

$$\gcd(n + 1, r) = \gcd(n + 1 - r, r) = \gcd(r, c) =1 $$

即 $n+1$ 与 $r$ 互素，对此计数，这恰是欧拉函数的定义。

答案即为

$$\sum_{n|N} \varphi(n + 1)$$

等等，因为要对对称的去重，所以再对这个结果 +1 除以 2 。因为 $(N, N)$ 只被计算了一次。

通过欧拉筛法，此题可以以 $\Theta(n)$ 的复杂度被解决。

#include <cstdio>

using namespace std;

const int N = 1000010;

int n, pc, ans;

bool vis[N];
int p[N], phi[N];

int main() {
    scanf("%d", &n);
    for (int x = 2; x <= n + 1; ++x) {
        if (!vis[x]) {
            p[++pc] = x;
            phi[x] = x - 1;
        }
        if (n % (x - 1) == 0)
            ans += phi[x];
        for (int i = 1; x * p[i] <= n + 1; ++i) {
            vis[x * p[i]] = true;
            if (x % p[i] == 0) {
                phi[x * p[i]] = phi[x] * p[i];
                break;
            } else {
                phi[x * p[i]] = phi[x] * phi[p[i]];
            }
        }
    }
    printf("%d\n", (ans + 1) / 2);
    return 0;
}