题解：P14533 [RMI 2018] 松鼠 / Squirrel

· · 题解

我们发现只有 \gcd(p-1,q-1)=1 时 (p,q) 才能被看到。证明也不难证，因为存在一个点 (\dfrac{p-1}{\gcd(p-1,q-1)}+1,\dfrac{q-1}{\gcd(p-1,q-1)}+1)，其与 (p,q) 和 (1,1) 共线。

所以考虑所有 \gcd(p-1,q-1)=1 且能跳到的点，记 x 为总步数，A 为 \max(m,n)，暴力做是 O(x \log n) 的，常数又大，无法通过。

预处理呢？预处理的时间复杂度 O(A^2)。时间复杂度达到 O(A^2+x)，常数小的话可能可以通过。

发现这个互质可以 bitset，只要不互质的为 1，互质的为 0，显然的，\gcd(a,pq)=1，当且仅当 \gcd(a,p)=1,\gcd(a,q)=1，于是只要有一个不与 a 互质，就可以判断出其乘积不与 a 互质了。这不就是或吗？

注意到 (1,2) 和 (2,1) 其实能够被看见。其余在第 1 行或第 1 列的就不能被看见了。所以预处理时就把 (0,1) 和 (1,0) 设置为互素的。

时间复杂度 O(\dfrac{A^2}{w}+x)，w=32，只需要不到两秒就能通过。

#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int N = 60009;
bitset<N> g[N];
int isPrime[N];
int m, n, F, ans;
//unordered_map<int, int> mp;

void f(int x, int y) {
    if (!g[x - 1][y - 1] && x >= 1 && x <= m && y >= 1 && y <= n)
        ans++;
}

void dfs(int x, int y, int p, int c) {
    if (p == 1) {
        if (c == 0)
            f(x - 1, y);
        if (c == 1)
            f(x, y - 1);
        if (c == 2)
            f(x + 1, y);
        if (c == 3)
            f(x, y + 1);
        return;
    }
    //f(x, y);
    if (c == 0) {
        for (int i = 1; i <= p; i++)
            x--, f(x, y);
        for (int i = 1; i <= p / 2; i++)
            x--, y--, f(x, y);
        dfs(x, y, p / 2, 0);
        dfs(x, y, p / 2, 1);
        x += p / 2;
        y += p / 2;
        for (int i = 1; i <= p / 2; i++)
            x--, y++, f(x, y);
        dfs(x, y, p / 2, 0);
        dfs(x, y, p / 2, 3);
    }
    if (c == 1) {
        for (int i = 1; i <= p; i++)
            y--, f(x, y);
        for (int i = 1; i <= p / 2; i++)
            x--, y--, f(x, y);
        dfs(x, y, p / 2, 1);
        dfs(x, y, p / 2, 0);
        x += p / 2;
        y += p / 2;
        for (int i = 1; i <= p / 2; i++)
            x++, y--, f(x, y);
        dfs(x, y, p / 2, 1);
        dfs(x, y, p / 2, 2);
    }
    if (c == 2) {
        for (int i = 1; i <= p; i++)
            x++, f(x, y);
        for (int i = 1; i <= p / 2; i++)
            x++, y++, f(x, y);
        dfs(x, y, p / 2, 2);
        dfs(x, y, p / 2, 3);
        x -= p / 2;
        y -= p / 2;
        for (int i = 1; i <= p / 2; i++)
            x++, y--, f(x, y);
        dfs(x, y, p / 2, 2);
        dfs(x, y, p / 2, 1);
    }
    if (c == 3) {
        for (int i = 1; i <= p; i++)
            y++, f(x, y);
        for (int i = 1; i <= p / 2; i++)
            x++, y++, f(x, y);
        dfs(x, y, p / 2, 2);
        dfs(x, y, p / 2, 3);
        x -= p / 2;
        y -= p / 2;
        for (int i = 1; i <= p / 2; i++)
            x--, y++, f(x, y);
        dfs(x, y, p / 2, 3);
        dfs(x, y, p / 2, 0);
    }
}

signed main() {
    //freopen("squirrel1.in", "r", stdin);
    //freopen("squirrel1.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> m >> n >> F;
    isPrime[1] = 0;
    for (int i = 2; i <= 51000; i++)
        isPrime[i] = 1;
    for (int i = 2; i * i <= 51000; i++) {
        if (isPrime[i])
            for (int j = i * i; j <= 51000; j += i)
                isPrime[j] = 0;
    }
    for (int i = 2; i <= 51000; i++)
        g[1][i] = 0, g[0][i] = 1;
    for (int i = 2; i <= 51000; i++) {
        g[i][1] = 0;
        g[i][0] = 1;
        if (isPrime[i]) {
            for (int j = i; j <= 51000; j += i)
                g[i][j] = 1;
        } else
            for (int j = 2; j <= sqrt(i); j++)
                if (i % j == 0) {
                    g[i] = g[j] | g[i / j];
                    break;
                }
    }
    for (int i = 1; i <= F; i++) {
        int x, y, p;
        cin >> x >> y >> p;
        f(x, y);
        dfs(x, y, p, 0);
    }
    cout << ans << endl;
    return 0;
}