[BZOJ4052][Cerc2013]Magical GCD

时间：2022-01-30 19:41:53

[BZOJ4052][Cerc2013]Magical GCD

试题描述

给出一个长度在 100 000 以内的正整数序列，大小不超过 10^12。 
求一个连续子序列，使得在所有的连续子序列中，它们的GCD值乘以它们的长度最大。

输入

本题为多组数据。

第一行一个整数 T，表示数据组数。

每组数据第一行为一个整数 n，表示序列长度；第二行为 n 个整数表示序列。

输出

对于每组数据，输出 max{ gcd * length }

输入示例





输出示例








数据规模及约定


见“试题描述”


题解


可以发现，随着子序列的增长，gcd 要么不变，若变化则变化后的 gcd 不会超过原来的 1/2，所以 gcd 的变化次数不会超过 log21012 = 12 · log210 次。


有了上面的结论，我们就可以枚举左端点，然后向右二分 gcd 即将变化的位置（维护区间 gcd 可以用 ST 表），在每个这样的位置更新答案，然后移动子序列右端点，重复这个过程。设数字大小为 A，那么更新答案次数为 log2A；每次二分需要 log2n；哦对了虽然 RMQ 询问复杂度 O(1)，但是每次需要取 gcd，最坏情况 log2A；别忘了我们还枚举了左端点有一个 n，所以最终复杂度不会超过 O(n · log22A · log2n)。




#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <stack>

#include <vector>

#include <queue>

#include <cstring>

#include <string>

#include <map>

#include <set>

using namespace std;

#define LL long long

const int BufferSize = 1 << 16;

char buffer[BufferSize], *Head, *Tail;

inline char Getchar() {

    if(Head == Tail) {

        int l = fread(buffer, 1, BufferSize, stdin);

        Tail = (Head = buffer) + l;

    }

    return *Head++;

}

LL read() {

    LL x = 0, f = 1; char c = Getchar();

    while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }

    while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }

    return x * f;

}

#define maxn 100010

#define maxlog 17

int n;

LL A[maxn];

LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }

LL Gcd[maxlog][maxn];

int Log[maxn];

void rmq_init() {

	Log[1] = 0;

	for(int i = 2; i <= n; i++) Log[i] = Log[i>>1] + 1;

	for(int i = 1; i <= n; i++) Gcd[0][i] = A[i];

	for(int j = 1; (1 << j) <= n; j++)

		for(int i = 1; i + (1 << j) - 1 <= n; i++)

			Gcd[j][i] = gcd(Gcd[j-1][i], Gcd[j-1][i+(1<<j-1)]);

	return ;

}

LL query(int l, int r) {

	int len = r - l + 1, t = Log[len];

	return gcd(Gcd[t][l], Gcd[t][r-(1<<t)+1]);

}

int main() {

	int T = read();

	while(T--) {

		n = read();

		for(int i = 1; i <= n; i++) A[i] = read();

		rmq_init();

		LL ans = 0;

		for(int L = 1; L <= n; L++) {

			int R = L; LL tmp = query(L, R);

			while(R < n) {

				int l = R, r = n + 1;

				while(r - l > 1) {

					int mid = l + r >> 1;

					if(query(L, mid) == tmp) l = mid; else r = mid;

				}

				R = l;

				ans = max(ans, tmp * (R - L + 1));

				R++; tmp = query(L, R);

			}

			if(R <= n) ans = max(ans, tmp * (R - L + 1)); // mark!!

		}

		printf("%lld\n", ans);

	}

	return 0;

}




大视野数据好强！我就因为少加 "mark!!" 那一行导致 WA 了一上午。。。
相关文章