2020-2021:teams:manespace:codeforc_round_641_div2_problem_c
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:codeforc_round_641_div2_problem_c [2020/05/15 12:47] intouchables |
2020-2021:teams:manespace:codeforc_round_641_div2_problem_c [2020/05/24 21:05] (当前版本) intouchables |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| =====Orac and LCM===== | =====Orac and LCM===== | ||
| - | 题意：给定长为 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（最大公约数） | + | 题目链接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>}(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代码===== | ||
| + | |||
| + | <code c++> | ||
| + | #include<bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | |||
| + | const ll mod = 998244353; | ||
| + | const int maxn = 2e5 + 5; | ||
| + | |||
| + | vector<int> ep[maxn]; | ||
| + | |||
| + | ll qpow(int k, ll b){ | ||
| + | ll res = 1; | ||
| + | while(b){ | ||
| + | if(b & 1) res *= k; | ||
| + | k *= k; | ||
| + | b >>= 1; | ||
| + | } | ||
| + | return res; | ||
| + | } | ||
| + | |||
| + | int main(){ | ||
| + | int n; scanf("%d", &n); | ||
| + | for(int i = 1; i <= n; i++){ | ||
| + | int t; scanf("%d", &t); | ||
| + | for(int i = 2; i * i <= t; ++i){ | ||
| + | ll cnt = 0; | ||
| + | while(t % i == 0){ | ||
| + | t /= i; | ||
| + | ++cnt; | ||
| + | } | ||
| + | ep[i].push_back(cnt); | ||
| + | } | ||
| + | if(t != 1) ep[t].push_back(1); | ||
| + | } | ||
| + | |||
| + | ll ans = 1; | ||
| + | for(int i = 1; i <= maxn; ++i){ | ||
| + | if(ep[i].size() >= n - 1){ | ||
| + | sort(ep[i].begin(), ep[i].end()); | ||
| + | if(ep[i].size() == n) ans *= qpow(i, ep[i][1]); | ||
| + | else ans *= qpow(i, ep[i][0]); | ||
| + | } | ||
| + | } | ||
| + | printf("%lld", ans); | ||
| + | } | ||
| + | </code> | ||
| + | |||
2020-2021/teams/manespace/codeforc_round_641_div2_problem_c.1589518077.txt.gz · 最后更改: 2020/05/15 12:47 由 intouchables
