本文共 3052 字，大约阅读时间需要 10 分钟。
为了解决这个问题，我们需要找到一个连续区间，使得这个区间内所有符卡的最大公约数乘以区间的长度最大的那个值。这个问题可以通过分治法来高效解决。
#include#include #include using namespace std;struct Result { int max_power; int current_gcd; int start_pos;};int gcd(int a, int b) { while (b != 0) { int temp = a % b; a = b; b = temp; } return a;}vector compute_prefix_gcd(const vector & a) { vector prefix(a.size(), 0); prefix[0] = a[0]; for (int i = 1; i < a.size(); ++i) { prefix[i] = gcd(prefix[i-1], a[i]); } return prefix;}vector compute_suffix_gcd(const vector & a) { vector suffix(a.size(), 0); suffix[a.size()-1] = a[a.size()-1]; for (int i = a.size()-2; i >= 0; --i) { suffix[i] = gcd(suffix[i+1], a[i]); } return suffix;}Result max_power(int left, int right, const vector & a, const vector & prefix, const vector & suffix) { if (left > right) return {0, 0, left}; if (left == right) return {a[left], a[left], left}; int mid = (left + right) / 2; Result left_res = max_power(left, mid, a, prefix, suffix); Result right_res = max_power(mid+1, right, a, prefix, suffix); int combined_gcd = gcd(left_res.current_gcd, right_res.current_gcd); int combined_length = right - left + 1; int combined_power = combined_gcd * combined_length; if (combined_power > left_res.max_power && combined_power > right_res.max_power) { return {combined_power, combined_gcd, left}; } int mid_gcd = gcd(a[mid], a[mid+1]); if (mid_gcd != left_res.current_gcd && mid_gcd != right_res.current_gcd) { mid_gcd = gcd(mid_gcd, a[mid]); mid_gcd = gcd(mid_gcd, a[mid+1]); } int mid_length = mid - left + 1; int mid_power = mid_gcd * mid_length; if (mid_power > left_res.max_power) { left_res.max_power = mid_power; } mid_length = right - mid; mid_gcd = gcd(a[mid+1], a[mid]); mid_power = mid_gcd * mid_length; if (mid_power > right_res.max_power) { right_res.max_power = mid_power; } if (left_res.max_power > right_res.max_power) { return left_res; } else { return right_res; }}int main() { int n; read(n); vector a(n); for (int i = 0; i < n; ++i) { a[i] = read(); } vector prefix = compute_prefix_gcd(a); vector suffix = compute_suffix_gcd(a); Result res = max_power(0, n-1, a, prefix, suffix); cout << res.max_power << endl; return 0;}
通过这种方法，我们可以高效地找到最大的魔力值。
转载地址：http://kloo.baihongyu.com/