A. 长春花
给定一个素数 p，对每个 0≤x<p，设 f(x) 表示一个最小的非负整数 a，使得存在一个非负整数 b，满足 (a2+b2)mod p=x。
现在，你想要求 max{f(0),f(1),⋯,f(p−1)} 的值。
解:直接暴力。
#include <bits/stdc++.h>
using namespace std;
mt19937 hua(20041115);
const int N = 5e5 + 50;
int sq[N];
int main() {
int p;
cin >> p;
memset(sq, -1, sizeof sq);
for (int i = 0; i < p; ++i)
sq[1ll * i * i % p] = i;
int mx = -1;
for (int i = 0; i < p; ++i) {
bool ok = false;
for (int a = 0; a < p; ++a) {
int b = ((i - 1ll * a * a) % p + p) % p;
if (sq[b] != -1) {
ok = true;
mx = max(a, mx);
break;
}
}
assert(ok);
}
cout << mx << '\n';
}
B. 紫罗兰
给定一张 n 个顶点 m 条边的无向图，顶点的编号在 1∼n 内，第 i 条无向边连接着顶点 xi 与 yi。我们称顶点 v0,v2,⋯,vk−1 构成了一个大小为 k 的环，当且仅当 k≥3，且对任意 0≤i<k，图中都存在一条连接顶点 vi 与 v(i+1)mod k 的无向边。我们称一个环 C 为最小环，当且仅当图中不存在一个大小严格小于 C 的环。
现在，你想要求出，图中有多少本质不同的最小环。
我们称两个环 C1(u0,u1,⋯,uk−1) 与 C2(v0,v1,⋯,vk−1) 不同，当且仅当组成这两个环的边不同。
解:
首先，我们求出图中的最小环长 。由于图中边无权，因此对于一个固定的顶点 ，我们可以使用 BFS在 的时间复杂度内计算出包含 的最小环的长度。具体地，我们维护 表示从 出发到顶点 的最短路。当我们从 第一次访问到一个顶点 时，更新其对应的 值，否则我们可以找到一个长度为 的环。注意到虽然我们不能保证该环为简单环，但注意到我们找到的所有环在去除公共部分后一定是一个简单环，因此我们对所有环取 min 一定可以得到最小环长。对于计数部分，我们直接在计算最小环长时顺便统计方案数即可.
我们发现：
- 以环上的任意一点为起点均会统计该环一次，因此答案要除以 。
- 当 为偶数时，每个环会从两个方向上各被统计一次，因此答案要额外再除以 。
#include <bits/stdc++.h>
using namespace std;
mt19937 hua(20041115);
const int N = 6005;
int n, m, dist[N], ways[N], len = 0x3f3f3f3f;
long long cnt = 0;
vector<int> G[N];
void gogo(int s) {
memset(dist, 0x3f, sizeof dist);
memset(ways, 0, sizeof ways);
queue<int> que;
que.push(s);
dist[s] = 0;
ways[s] = 1;
while (!que.empty()) {
int x = que.front(); que.pop();
for (int y : G[x]) {
if (dist[x] == dist[y] || dist[x] + 1 == dist[y]) {
int cyc = dist[x] + dist[y] + 1;
long long c = ways[x] * ways[y];
if (cyc < len) {
len = cyc;
cnt = c;
}
else if (cyc == len) {
cnt += c;
}
}
if (dist[y] > dist[x] + 1) {
dist[y] = dist[x] + 1;
ways[y] = ways[x];
que.push(y);
}
else if (dist[y] == dist[x] + 1) {
ways[y] += ways[x];
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for (int x = 1; x <= n; ++x) {
gogo(x);
}
if (len % 2) {
cnt /= len;
cnt /= 2;
}
else {
cnt /= len;
}
cout << cnt << "\n";
}