首页 > 代码库 > UVa 1642 (综合) Magical GCD

UVa 1642 (综合) Magical GCD

2024-10-22 11:34:39   210人阅读

题意：

给出一个数列，求一个连续的子序列，使得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


联系
我们