题解 P4388 【付公主的矩形】

· · 题解

逆向思考，考虑对于一组 (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;
}