专栏文章

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

zzhujianheng
P14533题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min5ozyt
此快照首次捕获于
2025/12/01 20:59
3 个月前
此快照最后确认于
2025/12/01 20:59
3 个月前
查看原文
我们发现只有 gcd⁡(p−1,q−1)=1\gcd(p-1,q-1)=1 时 (p,q)(p,q) 才能被看到。证明也不难证，因为存在一个点 (p−1gcd⁡(p−1,q−1)+1,q−1gcd⁡(p−1,q−1)+1)(\dfrac{p-1}{\gcd(p-1,q-1)}+1,\dfrac{q-1}{\gcd(p-1,q-1)}+1)，其与 (p,q)(p,q) 和 (1,1)(1,1) 共线。
所以考虑所有 gcd⁡(p−1,q−1)=1\gcd(p-1,q-1)=1 且能跳到的点，记 xx 为总步数，AA 为 max⁡(m,n)\max(m,n)，暴力做是 O(xlog⁡n)O(x \log n) 的，常数又大，无法通过。
预处理呢？预处理的时间复杂度 O(A2)O(A^2)。时间复杂度达到 O(A2+x)O(A^2+x)，常数小的话可能可以通过。
发现这个互质可以 bitset，只要不互质的为 11，互质的为 00，显然的，gcd⁡(a,pq)=1\gcd(a,pq)=1，当且仅当 gcd⁡(a,p)=1,gcd⁡(a,q)=1\gcd(a,p)=1,\gcd(a,q)=1，于是只要有一个不与 aa 互质，就可以判断出其乘积不与 aa 互质了。这不就是或吗？
注意到 (1,2)(1,2) 和 (2,1)(2,1) 其实能够被看见。其余在第 11 行或第 11 列的就不能被看见了。所以预处理时就把 (0,1)(0,1) 和 (1,0)(1,0) 设置为互素的。
时间复杂度 O(A2w+x)O(\dfrac{A^2}{w}+x)，w=32w=32，只需要不到两秒就能通过。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...