小白月赛 103 出题人题解

更新：

F 题经群友指出，存在测试数据 std 错误的情况。且目前暂时没有人能保证此题存在完全正确的、保证时空复杂度的解法。所以目前定义此题为“假题”。

本场比赛出题仓促，确实存在了相对较多的问题，很抱歉给部分参赛选手带来了不好的参赛体验。

E 题是赛前两天临时换上来了，明显地拼凑感很强，但是有一个点是，这个 E 还是弱化过的（就是临时换的第一个还是这个的强化版本）本题的另一个槽点这个 fg 的复合没用，原本那个版本是有点用的。弱化了是没啥用（出题人可能认为这没啥关系，属于出题人的误判了，之后注意）。

A

若能构成正多边形，正三角形一定是周长最小的正三角形。因为正多边形的周长为 $na$ 。

B

按题意循环判断即可。

一个简单实现是使用正则表达式 R"(^[a-zA-Z0-9.]+@[a-zA-Z0-9-.]+$)"，后按 @ 分开，就只需要判断长度和开头结尾是否有 . 和 - 了。

C

如果你使用打表，可以直接得到结论： $\begin{cases}1&&n\le2\\2^{\lceil\log{n}\rceil}&& n>2\end{cases}$ 。

证明：对于 $n$ 的最高位 $1$ ，仅保留这一位 $1$ ，对于低位可以任取，此时覆盖了 $n$ 最高位为 $1$ 的所有情况；然后 $n$ 的最高位 $1$ 这一位为 $0$ ，次高位为 $1$ ，对于低位可以任取，此时覆盖了 $n$ 次高位为 $1$ 的所有情况。依次类推，所以最小的不能被表示的就是 $2^{\lceil\log{n}}$ ， $n=1,2$ 特判。

D

距离两个点距离相等的点构成的直线是这两点连线的中垂线。

考虑怎么表示中垂线，中垂线经过两点的中点，斜率乘以这两点连线斜率 $=-1$ 。

考虑去重，维护直线斜截式 $y=kx+b$ 。 $k=\dfrac{y_1-y_2}{x_1-x_2},b=y-kx=\dfrac{y_1(x_1-x_2)-x_1(y_1-y_2)}{x_1-x_2}$ 。

中点坐标为 $(\dfrac{x_1+x_2}{2},\dfrac{y_1+y_2}{2})$ ，代入计算出分数，化为最简分数，注意分子分母的正负性，避免出现： $\dfrac{-1}{2}\neq \dfrac{1}{-2}$ 的情况。

求出 $(k,b)$ 后，重载一下分数的比较运算符，放入 set/map 去重即可。

特判 $x_1=x_2$ 和 $y_1=y_2$ 的情况。

还可以维护一般式： $Ax+By+C=0$ ，好处是不用重载分数比较，化简后都是整数。但是一样要考虑正负性，以及最简性。例如： $4x-6y+8=0$ 和 $-2x+3y-4=0$ 。

时间复杂度： $O(n^2\log n)$ 。

E

f,g 实际独立，分别考虑。

对于 f(x)，只要从 $n$ 扫到 $1$ ，过程中扫到 $b_i$ 时，标记其所有因子， $b_i$ 下一个不和 $b_i$ 互质的数即为 $b_i$ 的所有因子中出现最近的一个。因为 $b$ 是排列，所以所有因子规模是 $n\ln n$ 的。

对于 $g(x)$ 类似地，从 $n$ 扫到 $1$ ，过程中扫到 $a_i$ 时，标记其所有因子，表示其因子的倍数多了一个。因为 $x$ 的询问只和 $c[x]$ 有关，所有把 $x$ 放到 $c[x]$ 上询问，扫到 $c[x]$ 时， $x$ 被标记的次数即为 $g(x)$ 。

时间复杂度： $O(n\ln n)$ 。

因为 $n\le 10^5$ ，所以直接 $O(\sqrt n)$ 处理因子也可以。

#include<bits/stdc++.h>
#define For(i,a,b) for(i=a;i<=b;i++)
#define FOR(i,a,b) for(i=a;i>=b;i--)
using namespace std;
const int N = 1e5 + 10;
vector<pair<int, int>> Q[N];
int ans[N];
vector<int> fac[N];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<int> a(n + 1), b(n + 1), c(n + 1);
	int i;
	For(i, 1, n) cin >> a[i];
	For(i, 1, n) cin >> b[i];
	For(i, 1, n) cin >> c[i];
	vector<int> nex(n + 1, n + 1), last(n + 1, n + 1);
	For(i, 1, n) {
		int j;
		For(j, 1, n) {
			if (i * j > n) break;
			fac[i * j].push_back(i);
		}
	}
	FOR(i, n, 1) {
		nex[i] = n + 1;
		for (auto u : fac[b[i]]) {
			if (u == 1) continue;
			nex[i] = min(nex[i], last[u]);
		}
		if (nex[i] == n + 1) nex[i] = i;
		for (auto u : fac[b[i]]) {
			last[u] = i;
		}
	}
	For(i, 1, m) {
		int x;
		cin >> x;
		Q[c[gcd(b[x], b[nex[x]])]].push_back({i, gcd(b[x], b[nex[x]])});
	}
	vector<int> cnt(n + 1);
	FOR(i, n, 1) {
		for (auto u : fac[a[i]]) {
			cnt[u]++;
		}
		for (auto u : Q[i]) {
			ans[u.first] = cnt[u.second];
		}
	}
	For(i, 1, m) {
		cout << ans[i] << '\n';
	}
	return 0;
}