bzoj4052

gcd

跟那道cf题是一个原理。。。

每一时刻我们最多有log个gcd，那么我们用map存储每种gcd最左端，每次和新的数gcd就更新新的gcd的最左端，然后更新答案

#include<bits/stdc++.h> using namespace std; typedef long long ll; int n, T; map<ll, int> tmp_l, Left; ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); } int main() {int T;cin >> T;while(T --){scanf("%d", &n);Left.clear();ll ans = 0;for(int i = 1; i <= n; ++i) {ll x;scanf("%lld", &x);tmp_l.clear();for(map<ll, int> :: iterator it = Left.begin(); it != Left.end(); ++it){ll tmp = gcd(it -> first, x);int le = it -> second;if(tmp_l.find(tmp) == tmp_l.end()) tmp_l[tmp] = le;else tmp_l[tmp] = min(tmp_l[tmp], le);}if(tmp_l.find(x) == tmp_l.end()) tmp_l[x] = i;for(map<ll, int> :: iterator it = tmp_l.begin(); it != tmp_l.end(); ++it){ // printf("gcd = %lld len = %d\n", it -> first, (i - it -> second + 1));ans = max(ans, it -> first * (long long)(i - it -> second + 1));}swap(tmp_l, Left);}printf("%lld\n", ans);}return 0; } View Code

 

转载于:https://www.cnblogs.com/19992147orz/p/7490033.html

总结

以上是生活随笔为你收集整理的bzoj4052的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。