首页 > 代码库 > UVa 1642 (综合) Magical GCD
UVa 1642 (综合) Magical GCD
题意:
给出一个数列,求一个连续的子序列,使得MGCD(i, j) = 该子序列的长度(j-i+1) × 子序列的gcd 最大,并输出这个最大值。
分析:
感觉可能要用优先队列,但貌似也用不上。
但类似地,从左往右枚举右端点,不难发现随着序列长度的增大,其子序列的最大公约数是非递增的。一般情况下,是呈阶梯状递减的。于是我们只要保留相同的gcd中,左端点最小的那个序列(因为相同的gcd里面它的长度最大,MGCD就是最大的)。
右端点更新的时候,同时也要更新每个子序列的gcd,然后把重复的gcd的子序列去掉,只保留长度最大的那个。
这样就减少了很多重复的gcd的计算。
1 #include <cstdio> 2 #include <algorithm> 3 #include <vector> 4 using namespace std; 5 typedef long long LL; 6 7 const int maxn = 100000 + 10; 8 LL a[maxn]; 9 10 struct HEHE11 {12 LL g; //gcd13 int p; //起始位置14 HEHE(LL g=0, int p=0): g(g), p(p) {}15 bool operator < (const HEHE& rhs) const16 {17 return g < rhs.g || (g == rhs.g && p < rhs.p);18 }19 };20 21 LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); }22 23 int main()24 {25 int T, n;26 scanf("%d", &T);27 while(T--)28 {29 scanf("%d", &n);30 for(int i = 0; i < n; ++i) scanf("%lld", &a[i]);31 LL ans = 0;32 vector<HEHE> cur;33 for(int j = 0; j < n; ++j) //枚举右端点34 {35 cur.push_back(HEHE(0, j));36 for(int k = 0; k < cur.size(); ++k) //更新gcd的值37 cur[k].g = gcd(cur[k].g, a[j]);38 sort(cur.begin(), cur.end());39 40 vector<HEHE> nani;41 for(int k = 0; k < cur.size(); ++k)42 if(k == 0 || cur[k-1].g != cur[k].g)43 {//相同的gcd每次只取最开头的数44 nani.push_back(cur[k]);45 ans = max(ans, cur[k].g * (j - cur[k].p + 1));46 }47 cur = nani;48 }49 50 printf("%lld\n", ans);51 }52 53 return 0;54 }
UVa 1642 (综合) Magical GCD
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。