题目链接：https://codeforces.com/contest/1325
A - EhAb AnD gCd
题意：给一个正整数 (s(2 leq s leq 10^9)) ，构造两个正整数 (a,b) ，使得 (gcd(a,b)+lcm(a,b)=s) 。
题解：设 (a=xg,b=yg) 且 (gcd(x,y)=1) ，则 (gcd(a,b)=g,lcm(a,b)=frac{ab}{g}=xyg) ，原式为 ((xy+1)g=s) ，所以说只要分解出 (s) 的一个因子 (g(g eq s)) ，就可以构造出来。易知可以取 (g=1) 。
B - CopyCopyCopyCopyCopy
签到题。
题意：给一个 (n) 个数的数组，然后可以把这个数组复制粘贴 (n) 次（例如把 ([1, 2, 3]) 复制为 ([1, 2, 3, 1, 2, 3, 1, 2, 3])）。求复制粘贴之后的数组的最长上升子序列的长度。
题解：思考一下复制粘贴一次之后，最长上升子序列的变化，意思就是可以从头再选一次元素，那么很容易想到，只需要在每次复制粘贴的数组里面选一个尽可能小的元素，就可以弄出最长上升子序列，所以答案就是排序去重。
*C - Ehab and Path-etic MEXs
题意：给一棵 (n) 个节点的树，要求给每条边赋权值 ([0, n-1]) 。对于某个点对 ((u,v)) ，定义 (mex_path(u,v)) 的值就是简单路径 ((u,v)) 中经过的边的权值的集合的 (mex) ，就是那个SG函数里面用到的 (mex) ，返回值是这个集合中不存在的最小的自然数，例如 (mex({1,2,3,5})=0) ， (mex({0,1,2,4,5})=3) 。要求赋值的结果，最小化所有的点对 ((u,v)) 的最大 (mex_path(u,v)) 。
题解：思考了很久不知道怎么弄。不过后面突然想到了，是要使得权值小的边，尽可能不被大多数的路径经过？题目是要求最小化最大值，又不是最小化和。但是这个思路确实有启发。突然想到假如有一个“三岔路口”，那么假如给三条边赋值为 ([0,1,2]) ，那么显然每条简单路径至多经过其中的两条，也就是说 (mex_path) 值至多为 (2) 。只需要说明 ({0,1}) 不能被构造出来就能够证明 (2) 是最小值了。幸运的是，显然至少有一条边的 (mex_path) 值为1，就是那条权值为 (0) 的边。而只要 (ngeq 2) ，就一定有一条边，那条权值为 (0) 的边无论如何都会存在，所以 (0) 不能被构造。同理，假如有 (ngeq 3) ，那么那条同时包含权值为 (0,1) 两条边的路径的 (mex_path) 值至少为 (2) 。易知“三岔路口”至少需要4个点，所以拥有4个点的，且拥有“三岔路口”的，都可以通过这个方法构造。除此之外可以显然得到至多3个点的或者虽然点很多但依然是一条链的，肯定有一条简单路径是包含所有的边的，所以随便怎么构造都是对的。
当时写得比较冗余，其实这几种构造是可以合并在一起的，只需要取出度最多的点，尝试给其中的边分配 ([0,1,2]) （或者度最多的点不够，那也是分配最小的几个给他），其他的边是乱分配即可。
vector<int> G[100005];
int ans[100005];
void test_case() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n - 1; ++i) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(i);
G[v].push_back(i);
}
int id = 1;
for(int i = 1; i <= n; ++i) {
if(G[i].size() >= 3) {
id = i;
break;
}
}
int top = 0;
for(auto &i : G[id])
ans[i] = ++top;
for(int i = 1; i <= n - 1; ++i) {
if(ans[i] == 0)
ans[i] = ++top;
printf("%d
", ans[i] - 1);
}
}
*D - Ehab the Xorcist
题意：给定非负整数 (u,v(0leq u,v leq 10^18)) ，求最短的正整数数组，使得数组中所有元素的异或和为 (u) ，和为 (v) 。注意，若数组中没有元素，则异或和和和都是 (0)。无解输出 (-1) 。
题解：既然是最短，那么考虑哪些东西会是 (0) ，由于题目要求的都是正整数，所以只有当 (v=0) 的时候才有可能需要 (0) 个数，这时必定要 (u=0) ，否则若 (v=0) 且 (u > 0) ，直接无解。
那么从这里开始就有 (v>0) ，一种很显然的情况也是无解的，就是 (u>v) （前面的 (v=0) 且 (u>0) 也是这种情况）。要构造 (u) 的每个某个位的1，那么至少需要这个位的1这么大，所以和是不可能少于 (v) 的。其次有一种情况也是显然无解的，就是 (u,v) 的奇偶性不同，因为假如 (v) 是偶数，那么就需要偶数个个位1，但是偶数个个位1异或的结果必定是 (0) 。反之同理。
这时可以讨论掉答案为 (1) 的情况，显然这种情况的充要条件是 (u=v) ，根据上面已经把都是0的情况去掉了，所以这里不再判断0。
那么答案至少是 (2) 。
这种题目一般都会和 (u) 扯上什么关系，会不会先固定一个数是 (u) 呢？不妨先固定第一个数是 (u) ，那么剩下的数只需要异或互相抵消掉（相等），且和为 ((v-u)) 。这时通过“ (u<v) 且 (u,v) 的奇偶性相同”可以得到 ((v-u)) 是偶数，那么显然可以设 (x=frac{v-u}{2}) ，那么 ({u,x,x}) 就是一个答案为 (3) 的解。实验证明这种题目先固定掉一个与“异或”关联的条件总是凑效的，或许因为“异或”这个运算比起加法运算要简单，不涉及进位。
那么假如 (u,x) 可以合并在一起，就可以弄到答案是 (2) 的结果了，能够把两个数字合并在一起，就要求前后不发生影响，易知当 (u,x) 的二进制1都互相错开，那么可以合并在一起，换言之要求 (u;and;x=0) 。
不过怎么说明 (u;and;x eq 0) 的情况，不可以构造出答案是 (2) 呢？比赛的时候没想出来，最后乱蒙一个就上了。没想到还真是这样。
官方的题解指出，可以通过尝试构造来验证不可能答案是 (2) ，过程如下：
已知 (u;and;x eq 0) ，假设答案是 (2) ，不妨设构造出的两个数为 (a,b) ，这时满足 (a ;xor; b=u) ，且 (a+b=v) 。官方题解给出了一个从未见过的等式： (a+b=a ;xor; b + 2(a;and;b)) ，意思就是错开的二进制位直接保留1，都是0的位不用管，而都是1的位，则会产生一个进位。也就是说 (v=u+2(a;and;b)) 变形得 (a;and;b=x) ，代入已知得 ((a;xor;b);and;(a;and;b) eq 0) ，要使得这个方程成立，需要某个二进制位的结果使得左边为1，否则若左边的每个二进制位都是0，那么答案就是0。考虑一个二进制为，对 (a,b) 枚举所有的情况，显然发现只有当 (a=1,b=1) 的情况才有 ((a;and;b)=1) ，此时左边却为 (0) ，所以矛盾。
ll u, v;
void test_case() {
scanf("%lld%lld", &u, &v);
if(u == v) {
if(u == 0) {
puts("0");
return;
}
puts("1");
printf("%lld
", u);
return;
}
if(u > v) {
puts("-1");
return;
}
if((u & 1) != (v & 1)) {
puts("-1");
return;
}
ll tmp = (v - u) >> 1;
if((tmp ^ u) == (tmp | u)) {
puts("2");
printf("%lld %lld
", (tmp | u), tmp);
return;
}
puts("3");
printf("%lld %lld %lld
", u, tmp, tmp);
}
*E - Ehab's REAL Number Theory Problem
题意：从 (n(1leq nleq 10^5)) 个正整数的数组 (a) 中，选出最短的一个子序列，使得这个子序列的乘积是完全平方数。每个数 (a_i (1leq a_i leq 10^6)) 且 (a_i) 至多有 (7) 个因子。
题解：最诡异的限制条件是“ (a_i) 至多有 (7) 个因子” ，仔细推一推发现这个意思就是 (a_i) 至多有两种不同的质因子。然后我当时就考虑特判掉 (1) 以及两个相等的数的情况，然后是一些 (p) ，一些 (p*q) ，和一些 (p*q*q) 之间找一条首尾都是同种单数个因子的路径的，这个图都不知道怎么建，连路径都不一定找得到，别说是最短路径了。所以这道题就是完全不会的。
其实一个显然的思路是这样，因为 (1) 也是一个完全平方数，所以可以把所有其他的平方因子约掉，不影响答案，对每个数约掉平方因子，得到的结果只能是 (1,p,p*q) 三种类型。考虑对 (p*q) 这种类型的数，在图中连接 ((p,q)) ，考虑选择一个数对应走一条边，那么一个乘积是完全平方数的子序列就是一条路径，可以观察路径 (path(x,y)) 中，除了 (x,y) 只被走了一次，其他的都被走了两次，必定是平方因子，且子序列的长度就是路径的边数，要求整个乘积都是平方的因子就要 (x=y) ，换言之就是要求最短环。仔细想想这种情况可以推广到 (1,p) 的情况，首先可以特判掉 (1) ，这种数自己就是一个完全平方数且不可能有东西比它更短，假如给 (1) 连接一个自环，也可以合并到这种情况，当然特判掉更简单。对于 (p) ，假如有两个 (p) ，在特判掉 (1) 之后，答案是 (2) 的就是最短子序列，也可以继续特判。否则这个 (p) 是没得配的（错误，例如：2 2*3 3*5 5*7 7）。够无聊的话，也可以连接 ((1,p)) 这样有两个 (p) 的时候就会走一次1然后回来，也是最小环（提示我们有时候可以把 (1) 看作“质数”）。那么剩下的这些 (p*q) 的最小环怎么算呢？我昨晚只知道一种 (O(n^3)) 的Floyd算法，题解和qls给出了一种 (O(n^2)) 的算法，首先枚举每个要求环的点 (i) ，然后以 (i) 为源点进行一次bfs，找出整棵bfs树。当某条非树边可以“追溯”（就是求双连通分量的那个回溯，指通过非树边去到另一棵子树，然后沿子树的父亲上升到 (i) 点）到 (i) 点，那么这条非树边就可以和bfs树上的东西形成一个环，这些环就是包含 (i) 点的环。注意这条“非树边”，既不可能可能是“前向边”，也不可能是“后向边”（虽然有可能指向父亲，但毕竟这是无向图，这时是“树边”的反边），也有可能是横叉边（连接同一层的不同节点，甚至是某个节点的自环）。
具体来说，假如当前节点是 (u) ，边指向的节点是 (v) ，若 (v) 已经被访问过，且 (dep[u]>dep[v]) ，则这个一定是“树边”的反边或者“横叉边”，且一定有 (dep[u]=dep[v]+1) ，直接跳过（虽然横叉边可以更新答案，但是可以交给另一端来更新）；若 (v) 已经被访问过，且 (dep[u]=dep[v]) 则这个一定是“横叉边”，可以更新环为 (dep[u]+dep[v]+1) ；否则， (v) 已经被访问过，且 (dep[u]<dep[v]) 则这个一定是“横叉边”，而且一定满足 (dep[u]+1=dep[v]) （若不然，按照bfs的性质，(v) 的父亲就应该是 (u) ） ，可以更新环为 (dep[u]+dep[v]+1) 。
注意到其实无向图bfs中，边连接的点的深度改变都是只有1（经过assert验证）。为什么没有“前向边”？因为bfs的次序决定了，在取出这个目标节点的时候，要么它在其他搜索树中搜索过了，变成了“横叉边”，要么没有搜索过，变成了“树边”。同理也不会有“后向边”，或者说“后向边”一定变成是某条树边的反边。
解决了怎么求最小环之后，问题在于 (O(n^2)) 还是太大了。这里要惊人地注意到，由于 (a_i leq 10^6) ，那么所有 (p*q(p<q)) 这种形式的数，必有小的那个因子(p (p<10^3)) 。所以不需要考虑从 (q(q>10^3)) 出发的最小环，因为从 (q) 出发走第一步是不能走到其他 (q'(q'>10^3)) 的，必须要往小的 (p) 走第一步。否则，若连接有 ((q,q')) ，则说明有一个数 (a_igeq q*q' >10^6) 。
也就是说，最小环若存在必定包含至少一个 (p(p<10^3)) ，那么只需要对 (p(p<10^3)) 进行bfs即可。
const int MAXN = 1e6;
int p[MAXN + 5], ptop;
int pm[MAXN + 5], pid[MAXN + 5];
void sieve() {
int n = MAXN;
p[0] = 1;
pm[1] = 1;
pid[1] = 0;
for(int i = 2; i <= n; ++i) {
if(!pm[i]) {
p[++ptop] = i;
pm[i] = i;
pid[i] = ptop;
}
for(int j = 1; j <= ptop; ++j) {
int t = i * p[j];
if(t > n)
break;
pm[t] = p[j];
if(i % p[j] == 0)
break;
}
}
}
int a[100005];
int fj(int x) {
int d = 1;
while(x > 1) {
int p = pm[x];
x /= p;
if(d % p == 0) {
d /= p;
continue;
}
d *= p;
}
return d;
}
vector<int> G[1000005];
int ans;
int dep[1000005];
queue<int> Q;
void bfs(int s) {
for(int i = 0; i <= ptop; ++i)
dep[i] = -1;
while(!Q.empty())
Q.pop();
dep[s] = 0;
Q.push(s);
while(!Q.empty()) {
int u = Q.front();
Q.pop();
for(auto &v : G[u]) {
if(dep[v] == -1) {
dep[v] = dep[u] + 1;
if(dep[v] + dep[u] + 1 >= ans)
continue;
Q.push(v);
continue;
}
if(dep[v] >= dep[u]) {
ans = min(ans, dep[v] + dep[u] + 1);
continue;
}
}
}
}
void test_case() {
int n;
scanf("%d", &n);
sieve();
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
a[i] = fj(a[i]);
}
sort(a + 1, a + 1 + n);
if(a[1] == 1) {
puts("1");
return;
}
int m = unique(a + 1, a + 1 + n) - (a + 1);
if(m < n) {
puts("2");
return;
}
for(int i = 1; i <= m; ++i) {
int x = pid[pm[a[i]]], y = pid[a[i] / pm[a[i]]];
G[x].push_back(y);
G[y].push_back(x);
}
ans = INF;
for(int i = 0; i <= ptop && p[i] <= 1000; ++i)
bfs(pid[p[i]]);
if(ans == INF)
ans = -1;
printf("%d
", ans);
}
收获：
1、考虑“最小质因子”的取值，经常可以使得复杂度退化到根号，也注意那种不能分成两个质因子的数，是否和那些可以分成两个质因子的数不一样，可以分开处理。
2、把1看作第0个质数。这样那种 (p_1) 类型的和 (p_2) 类型的就可以通过1连接成一个环。否则，要特殊处理两端分别是 (p_1) 和 (p_2) 的情况，注意到中间确实还是会经过一些小的质数，所以复杂度不会改变。具体的做法应该是在枚举小质数作为源点的时候，若更新到含有单个 (v) 的节点 (v) 则记录一个最小深度+1。若找到两个这样的单个的 (v_1,v_2) ，就把这个值拿去更新答案。由前面排序去重可知，找到的 (v_1,v_2) 必定不同。
3、图的最小环，可以从每个点开始跑一次bfs，得到包含这个点的最小环。具体的做法是拿bfs中的“非树边”，也就是“横叉边”来接通两棵树。（若没有经过排序去重，则有时候这个“横叉边”有可能以多重边的形式存在，例如2 6 6，都是从2走到3，遍历s的时候把3推入队列中两次，这时要把从2（源点）出发的不同的多重边(2,3)，看作不同的子树，这样就依然是“横叉边”）。“横叉边”连接的是已遍历的节点，他可能连接同一层的节点，也可能连接下一层的节点，也可能连接上一层的节点。注意区分“树边”是只能连接下一层的未遍历节点，或者上一层的已遍历节点（父亲）。这时，若仅当某条边访问已遍历的同一层或者下一层的节点，就可以只取出“横叉边”，其中遍历同一层的“横叉边”被取出两次，连接不同层的“横叉边”只取出一次。
4、天大的bug，在bfs里面清空dep数组的时候，忘记改成离散化坐标/忘记对应原坐标，这种bug通过神奇的assert检测出来了，意思是可以在区域赛拼命交assert，找到那个RE的点？这里是因为assert一个 (dep[v]<dep[u]) 等价于 (dep[v]=dep[u]-1) 失败发现的。
*F. Ehab's Last Theorem
前一题是无向图的bfs，无向图的bfs是没有“前向边”和“后向边”的，只有“树边”和“横叉边”。
无向简单图bfs
若指向的节点未被访问：
是“树边”。
若指向的节点已经被访问：
指向深度较小的节点的边，要么是“树边”的反边，要么是“横叉边”，可以通过记录bfs树上的父亲来判断。
指向深度较大的节点的边，是“横叉边”。
指向深度相等的节点的边，是“横叉边”。
这一题是无向图dfs，无向图的dfs是没有“横叉边”的（在结束对这个子树的搜索之前，不会去访问下一个子树），“前向边”（或者“树边”，假如是父子关系）和“后向边（或者“树边”的反边，假如是父子关系）”成对出现。
无向简单图dfs
若指向的节点未被访问：
是“树边”。
若指向的节点已经被访问：
指向深度较小的节点的边，要么是“树边”的反边，要么是“后向边”，可以通过记录dfs树上的父亲来判断。
指向深度较大的节点的边，是“前向边”。
不可能指向深度相等的节点。
参考资料：[Tutorial] The DFS tree and its applications: how I found out I really didn't understand bridges
题意：给一个 (n) 个点， (m) 条边的无向简单图，记 (sq=lceil sqrt{n} ceil) ，要求找一个长度大于等于 (sq) 的简单环（A simple cycle is a cycle that doesn't contain any vertex twice. 也就是没有“8”字形的，或者说“8”字形的是两个简单环），或者找一个大小 恰好 为 (sq) 的独立集。
题解：记 (sq=lceil sqrt{n} ceil) 从任意一个点开始dfs，取出dfs树。注意区分“树边”的反边和“后向边”的区别，在这个无向简单图中，指向自己父亲的边，就是“树边”的反边，是不能算作“后向边”的。若某个点拥有不少于 (sq-2) 条“后向边”，那么选择“后向边”指向的点中深度最小的点走回去，就找到了一个长度不少于 (sq) 的环，因为是无重边无自环的简单图， (sq-2) 条“后向边”意味着有 (sq-2) 个不同的非父亲祖先，加上父亲和自己就有 (sq) 个点了。否则，若不存在这样的环，从dfs树中深度最大的点开始选择独立集。首先先把深度最大的点给选了，然后其“后向边”指向的非父亲祖先和其父亲都不能再选，由于选择某个点至多会导致其至多 (sq-1) 个祖先不能再选，那么每步选择最多会减少 (sq) 个点，显然这样是可以选到不少于 (sq) 个点的独立集的。
理清一下 (sq) 中上整的问题，比如 (n=7) ，那么 (sq=3) ，意味着选一个点至多会总共减少 (sq=3) 个点，选了2个之后最后还是会剩下至少1个点，所以可以选 (sq) 次。
具体实现的时候也需要从深度最大的点开始选，否则搞一个菊花图，就卡掉了。而且发现在实现的时候不需要区分“树边”的反边和“后向边”的区别。
int n, m, sq;
vector<int> G[100005];
int dep[100005];
int pa[100005];
pii tmp[100005];
int vis[100005];
void dfs(int u, int p) {
dep[u] = dep[p] + 1;
pa[u] = p;
int cnt = 1, mindepv = u;
for(auto &v : G[u]) {
if(dep[v] == 0) {
dfs(v, u);
continue;
}
if(dep[v] < dep[u]) {
++cnt;
if(dep[v] < dep[mindepv])
mindepv = v;
}
}
if(cnt >= sq) {
cnt = 0;
int cur = u;
++cnt;
while(cur != mindepv) {
cur = pa[cur];
++cnt;
}
printf("2
%d
", cnt);
printf("%d", u);
cur = u;
while(cur != mindepv) {
cur = pa[cur];
printf(" %d", cur);
}
printf("
");
exit(0);
}
}
void test_case() {
scanf("%d%d", &n, &m);
for(sq = 1; sq * sq < n; ++sq);
while(m--) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, 0);
for(int i = 1; i <= n; ++i)
tmp[i] = {dep[i], i};
sort(tmp + 1, tmp + 1 + n, greater<pii>());
printf("1
");
int cnt = 0;
for(int i = 1; i <= n; ++i) {
int u = tmp[i].second;
if(vis[u])
continue;
if(cnt != 0)
printf(" ");
printf("%d", u);
vis[u] = 1;
for(auto &v : G[u])
vis[v] = 1;
++cnt;
if(cnt == sq) {
printf("
");
exit(0);
}
}
}