2020-2021:teams:manespace:codeforces_round_641_div._2
比赛链接https://codeforc.es/contest/1350
CN的题真要命
A
题意：t次操作，每次给定n，k，求k次$n=n+f(n)$之后的n值，其中$f(n)$求取n的最小质因子。
题解：签到（之后就罚坐）题，分三类情况：
- 偶数最小质因子就是2，加完还是偶数，直接 $n + 2k$
- 非质奇数加一次最小质因子后会变偶数，所以 $n + f(n) + 2(k-1)$
- 质数第一次必定加本身，变成偶数，所以 $n*2 + 2(k-1)$
$1≤n≤2*10^6$，$1≤t≤10^2$，暴力不放心可以线性筛
B
题意：t次询问($1≤t≤10^2$)，每次给定长为 n ($1≤n≤10^5$)的正整数序列{s1,s2,…,sn}，求子序列满足对任意$i≤j$有si < sj且j % i == 0的最长子序列长度
题解：不难想到LIS，dp可以过，注意一下细节防止TLE
C
题意：给定长为n ($2≤n≤10^5$)的正整数序列{s1,s2,…,sn}，求任意两元素LCM（最小公倍数）组成新序列的GCD（最大公约数）
题解：咕咕咕
D
题意：t次询问，每次给定长为n的正整数序列
E
F
没看，不补
2020-2021/teams/manespace/codeforces_round_641_div._2.1589364585.txt.gz · 最后更改: 2020/05/13 18:09 由 intouchables
