======Codeforces Round #641 (Div. 2)======

=====A.Orac and Factors=====

====题目大意====

对于一个数 $n ≤ 10^6$ ，找到它最小的不是1的约数，然后加在这个值上，重复 $k ≤ 10^9 $次

====解题思路====

首先对于偶数，这个数一定是 2，而对于奇数，一次操作之后就会变成偶数，答案是显然的。

=====B.Orac and Models=====

====题目大意====

给定一个数列$ a_n  (n \le 1e6) $, 求一个最长子列，满足其前一个的下标是后一个的因数且 $a_j  > a_i $.

====解题思路====

这题显然就用一个 DP 就能在 $ O( nlogn ) $ 的时间内解决了.

=====C.Orac and LCM=====

====题目大意====

给定一个数列 $ s_n (n \le 100000) $ ,令 $ t = \{ lcm({a_i,a_j})|i < j \} $ ,求 $ gcd(t) $

====解题思路====

考虑对每个素数因子进行分析，经过$ lcm,gcd $操作之后相当于求每个因子在所有数中出现次数倒数第二小的次数并相乘，模拟即可。

注意：可以通过先提取出前两个数所含因子来显著减小复杂度

=====D.Orac and Medians=====

====题目大意====

给定一个数列 $ a_n (n \le 100000 ，1 \le a_i \le 1e9) $ , 再给定一个数 $k (1 \le k \le 1e9) $, 问能否通过把一个区间全部变成它的中位数的方式使序列全部变成$ k $.

====解题思路====

首先，如果不存在 $ k $,那么答案肯定是否， 在存在 $ k $ 的情况下 ，如果 $ k $ 旁边有大于 $ k $ 的数，那么我们显然可以通过将这个数变成 $ k $ 和原本 $ k $ 的区间将别的数都变为 $ k $, 进而我们发现，如果连续三个中存在两个 $\ge k$ ,那么可以通过区间操作将大于 $k$ 的数移到 $k$ 的旁边，若不存在，则不可能实现 (可以证明任意区间都会被变成小于 $k$ 的区间)。

=====E.Orac and Game of Life=====

====题目大意====

给定一个 $ n \times m 的 01 矩阵 (1 \le n,m \le 1000)$, 每个时间一个周围存在不同类型点的点的类型会发生改变 $ (0 \rightarrow 1, 1 \rightarrow 0) $ 给定 $ t \le 100000 $ 个询问，每次问 $ i , j $ 位置上 $ p $ 时间的类型。

====解题思路====

我们发现这个模型具有“传染”的性质，即上一时间变了的点周围没变的点，在下一时间会变且之后一直保持变的状态，因此我们只需要通过 $BFS$ 一次求出每个点开始变的时间并计算最后状态即可。

<del> F不会 </del>