小白月赛 103 出题人题解
更新：
F 题经群友指出，存在测试数据 std 错误的情况。且目前暂时没有人能保证此题存在完全正确的、保证时空复杂度的解法。所以目前定义此题为“假题”。
update on 2025.4.9 经过再次验题数据已更新。
本场比赛出题仓促，确实存在了相对较多的问题，很抱歉给部分参赛选手带来了不好的参赛体验。
E 题是赛前两天临时换上来了，明显地拼凑感很强，但是有一个点是，这个 E 还是弱化过的（就是临时换的第一个还是这个的强化版本）本题的另一个槽点这个 fg 的复合没用，原本那个版本是有点用的。弱化了是没啥用（出题人可能认为这没啥关系，属于出题人的误判了，之后注意）。
A
若能构成正多边形，正三角形一定是周长最小的正三角形。因为正多边形的周长为 。
B
按题意循环判断即可。
一个简单实现是使用正则表达式 R"(^[a-zA-Z0-9.]+@[a-zA-Z0-9-.]+$)"，后按 @ 分开，就只需要判断长度和开头结尾是否有 . 和 - 了。
C
如果你使用打表，可以直接得到结论：。
证明：对于 的最高位
，仅保留这一位
，对于低位可以任取，此时覆盖了
最高位为
的所有情况；然后
的最高位
这一位为
，次高位为
，对于低位可以任取，此时覆盖了
次高位为
的所有情况。依次类推，所以最小的不能被表示的就是
，
特判。
D
距离两个点距离相等的点构成的直线是这两点连线的中垂线。
考虑怎么表示中垂线，中垂线经过两点的中点，斜率乘以这两点连线斜率 。
考虑去重，维护直线斜截式 。
。
中点坐标为 ，代入计算出分数，化为最简分数，注意分子分母的正负性，避免出现：
的情况。
求出 后，重载一下分数的比较运算符，放入 set/map 去重即可。
特判 和
的情况。
还可以维护一般式：，好处是不用重载分数比较，化简后都是整数。但是一样要考虑正负性，以及最简性。例如：
和
。
时间复杂度：。
E
f,g 实际独立，分别考虑。
对于 f(x)，只要从 扫到
，过程中扫到
时，标记其所有因子，
下一个不和
互质的数即为
的所有因子中出现最近的一个。因为
是排列，所以所有因子规模是
的。
对于 类似地，从
扫到
，过程中扫到
时，标记其所有因子，表示其因子的倍数多了一个。因为
的询问只和
有关，所有把
放到
上询问，扫到
时，
被标记的次数即为
。
时间复杂度：。
因为 ，所以直接
处理因子也可以。
#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;
}
