2020-2021:teams:manespace:codeforc_round_641_div2_problem_c
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:codeforc_round_641_div2_problem_c [2020/05/15 15:47] 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 | ||
| + | |||
| + | =====推荐理由？===== | ||
| + | |||
| + | 思维题，挺思维的，嗯。 | ||
| =====题意===== | =====题意===== | ||
| - | 给定长为 n ($2≤n≤10^5$)的正整数序列{s<sub>1</sub>,s<sub>2</sub>,…,s<sub>n</sub>}，求由任意两元素 LCM（最小公倍数）组成新序列{a<sub>1</sub>,a<sub>2</sub>,…,a<sub>n</sub>}的 GCD（最大公约数） | + | 给定长为 n ($2≤n≤10^5$)的正整数序列{s<sub>1</sub>,s<sub>2</sub>,…,s<sub>n</sub>}，求由任意两元素 LCM（最小公倍数）组成新序列{a<sub>1</sub>,a<sub>2</sub>,…,a<sub>n</sub>}(1$≤$a<sub>i</sub>$≤2*10^5$)的 GCD（最大公约数），即LCM(GCD(s<sub>i</sub>,s<sub>j</sub>))($i ≤j$) |
| =====题解===== | =====题解===== | ||
| - | 啊好，还没写呢 | + | 将答案 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 | ||
| ------ | ------ | ||
| - | AC代码 | + | =====AC代码===== |
| <code c++> | <code c++> | ||
2020-2021/teams/manespace/codeforc_round_641_div2_problem_c.1589528842.txt.gz · 最后更改: 2020/05/15 15:47 由 intouchables
