Codeforces #641
Codeforce #641 div2
A.数学
B.DP
C.数学
D.数学

A.数学

给定n,k

你现在要操作k次，每次操作中，你找出n的最小非1因子，把它加回给n

如6，最小因子是2,6加上2是8,8最小因子是2,8加上2是10

思路：奇数+奇数=偶数偶数+偶数=偶数

只要找到第一个最小因子，加上，再加上2 * （ k - 1 ）即可

ac:

B.DP

给定一个序列

现在让你选一个最长子序列，使得它严格递增，并且后一项的位置标号能整除前一项的位置标号

思路：

枚举某个位置的所有标号因子，看是否满足大于的条件，满足->更新状态

给定n个数

你现在对这n个数两两求lcm（最小公倍数），然后求这些lcms的gcd（最大公因数）

思路：

首先所有数的gcd，肯定是答案的因子，把它先算出来，所有原数据再除以它，处理成新数

接下来对于某个数如果它没某个因子k，而其他数均有因子k，

那么显然两两算lcm的时候，每个lcm均有这个因子，所以我们统计一下这个因子即可

不过值得注意的一点是如果8被计算了，那么2,4，就不能被算，否则会重复

ac：

给定一个序列，一个数k

现在你有一个操作，就是选定一个区段，把该区段的所有数均改为此区段的中位数（如果有两个选较小者）

问是否可以通过若干次操作使得此序列全为k

思路：

对于区段的修改是选小不选大

所以如果一个比k大的数与k相邻，那么比它大的那个数一定能被修改成为k

进一步我们简单推理一下，当k本身出现过，并且存在相邻的两个数大于等于k，那么全序列一定可以被改成k

这题比较容易忽视的一点是如下情况：

大小大

这样跳一位的情况同样也可以通过一步修改使得它出现相邻满足的情况

ac：