2020-2021:teams:manespace:codeforces_642_div2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:manespace:codeforces_642_div2 [2020/05/16 17:35] iuiou [B] |
2020-2021:teams:manespace:codeforces_642_div2 [2020/05/16 18:00] (当前版本) iuiou |
||
|---|---|---|---|
| 行 24: | 行 24: | ||
| } | } | ||
| </code> | </code> | ||
| + | |||
| + | ==== C ==== | ||
| + | 题意：大致意思是，给定一段序列，然后任取两个数取其最小公倍数，然后放入新序列，问将所有情况取遍后，那整个序列的最大公约数。 | ||
| + | |||
| + | 解：数论……脑阔疼…… | ||
| + | |||
| + | **官方版**：听说巨佬推出公式，<del>反正我是不会推</del>，对于序列{a<sub>i</sub>}(1≤i≤n),有一个公式为：gcd({a<sub>i</sub>,a<sub>j</sub>})== lcm{a<sub>i</sub>,gcd(a<sub>j</sub>)}(1≤j≤n且j≠i)则这里a<sub>j</sub>取遍所有可能情况，这样我们就可以，预处理出，gcd的前缀，然后再求gcd。 | ||
| + | |||
| + | **暴力版**:太难了，我只会暴力……记过一系列简单计算，不难发现，结果即为，将所有数的素因子集合起来，筛选出在序列中出现过至少n-1次的素因子(否则答案中一定不存在)，对于所有满足条件的素因子i，遍历一遍序列求出序列所有数中素因数分解式中i的指数，取第二大的，则答案的素因数分解中一定存在这个项。接下来线性筛暴力筛出所有素数然后暴力循环找即可。 | ||
| + | |||
| + | ==== D ==== | ||
| + | 题意：给一段序列，给定一个数k，操作为：每次取一段区间，求出区间中位数，将区间所有数变成那个数，问能不能全刷成给定的数。 | ||
| + | |||
| + | 解：找规律的题，找不出来就罚坐(<del>真毒瘤</del>)，大致我们要判定这样一件事情，只有一个数，判定是不是那个数，给许多数，若序列中都不存在那个数，明显不满足，若满足，则是否存在三个数(两个数就判定两个数),满足有两个数大于等于k。 | ||
2020-2021/teams/manespace/codeforces_642_div2.1589621740.txt.gz · 最后更改: 2020/05/16 17:35 由 iuiou
