2022.11.17

T1

给你一个质数，让你求

首先，观察到，答案很小（最大的大样例也只有 \(16\) ），于是就打了个质数表，跑了下最大的质数看看，答案最大也就是31,于是很明显，\(a\) 的最大值就到31，一个很小的范围，直接考虑暴力。

为什么考场上只写了60：因为太暴力了，有很多东西都是重复计算的，可以优化掉

代码如下：

/*

　　　　　／＞　   フ
　　　　　| 　_　 _|
　 　　　／`ミ _x 彡
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

*/

#include<bits/stdc++.h>
using namespace std;

long long read()
{
    long long x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

int n, ans = 0;

int a[100010];

int main()
{
	n = read();
	for(int i = 0; i <= n; i++) a[i] = 2e9;
	for(int i = 0; i <= 31; i++)
	{
		for(int j = 0; j <= 50000; j++)
		{
			long long k = (1ll * i * i + 1ll * j * j) % n;
			a[k] = min(a[k], i);
		}
	}
	for(int i = 1; i < n; i++)
	{
		if(a[i] < 2e9)
		{
			ans = max(ans, a[i]);
		}
	}
	cout << ans;
    return 0;
}

T2

给你一个无向图，让你找出图中的最小环，并计数

首先考场思路，环肯定不止是三元环，但是多了的话又不会处理，看四个样例三个给的都是三元环。

所以直接枚举三个点判断是否成环，得到三元环，喜提50分

下面考虑正解：

首先，我们想到，跑最短路，如果用当前点更新一个