2020-2021:teams:manespace:codeforc_round_641_div2_problem_c
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:codeforc_round_641_div2_problem_c [2020/05/16 15:59] intouchables [题解] |
2020-2021:teams:manespace:codeforc_round_641_div2_problem_c [2020/05/24 21:05] (当前版本) intouchables |
||
|---|---|---|---|
| 行 2: | 行 2: | ||
| 题目链接https://codeforc.es/contest/1350/problem/C | 题目链接https://codeforc.es/contest/1350/problem/C | ||
| + | |||
| + | =====推荐理由？===== | ||
| + | |||
| + | 思维题，挺思维的，嗯。 | ||
| =====题意===== | =====题意===== | ||
| 行 10: | 行 14: | ||
| 将答案 ans 质因数分解，有 $ans =$ p<sub>1</sub><sup>k1</sup>p<sub>2</sub><sup>k2</sup>...p<sub>m</sub><sup>km</sup> | 将答案 ans 质因数分解，有 $ans =$ p<sub>1</sub><sup>k1</sup>p<sub>2</sub><sup>k2</sup>...p<sub>m</sub><sup>km</sup> | ||
| + | |||
| + | 对于每个 p<sub>i</sub>，一定在序列 s 中出现至少 $n - 1$ 次，每次出现由小到大可能为 p<sub>i</sub><sup>c1</sup>， p<sub>i</sub><sup>c2</sup>， ...p<sub>i</sub><sup>cki</sup> | ||
| + | |||
| + | GCD(LCM(p<sub>i</sub><sup>c1</sup>， p<sub>i</sub><sup>c2</sup>， ...p<sub>i</sub><sup>cki</sup>))一定为第二小的c2 | ||
| + | |||
| + | 所以可以对序列 s 每个数的每个质因子统计次数，将大于 $n-1$ 次的因子幂次方排序，取第二小累乘即可 | ||
| + | |||
| + | 注意用vector，不要处处longlong，否则会MLE | ||
| ------ | ------ | ||
2020-2021/teams/manespace/codeforc_round_641_div2_problem_c.1589615988.txt.gz · 最后更改: 2020/05/16 15:59 由 intouchables
