自动搬运

查看原文

来自洛谷，原作者为

	Ferm_Tawn Academic Off | 关注数永远小于粉丝 | 支持 红+300粉/5级勾+红/蓝勾/金勾/紫名 互关 | 互/杀关请私

搬运于2025-08-24 22:57:39，当前版本为作者最后更新于2024-02-04 12:39:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

显然，要获得最大经验值就是枚举所有有经验值的 $(x,y)$。

首先要解决的是如何快速求出 $l \sim r$ 的 $\gcd$ 值，可以用 $st$ 表来进行实现，单次查询复杂度为 $O(\log n)$ , 没学过的人请转步 P3865, $st$ 表预处理和查询代码如下：

void Init(int n){
    lg[1] = 0;
    for(int i = 2 ; i <= n ; i++) lg[i] = lg[i >> 1] + 1;
    for(int i = 1 ; i <= n ; i++) st[i][0] = a[i];
    for(int j = 1 ; j <= lg[n] ; j++){
        for(int i = 1 ; i + (1 << j) - 1 <= n ; i++) st[i][j] = __gcd(st[i + (1 << (j - 1))][j - 1] , st[i][j - 1]);
    }
}
int Find(int l , int r){
    int x = lg[r - l + 1];
    return __gcd(st[l][x] , st[r - (1 << x) + 1][x]);
}

接下来就是考虑如何快速算出所有经验值的总和。

这里复杂度是 $O(n \log^2 n)$ 。

这里给出的做法是枚举 $x$ ，二分查找 $y$ 。

先给出一个显而易见的定理：若 $\gcd(a_1,a_2 ,\cdots , a_L)= 3$ 且 $\gcd(a_1,a_2,\cdots , a_R ) = 3$ ，则对于 $L \le k \le R$ ，$\gcd(a_1,a_2 ,\cdots , a_k)= 3$ 。

若求出 $L \operatorname{and} R$ ，就可以求出以 $x$ 为左端点的 $\operatorname{score_{x,y}}$ 的总和了。

题解中只写出 $\gcd(a_x , a_{x + 1} , \dots , a_y)=3 , \operatorname{len \ mod} 2 = 1$ 的情况，另一种情况本质上是一样的。

对于这种情况，先对 $R$ 进行二分答案，其中二分的是 $R$ 在第几个 $\operatorname{len}$ 长度为奇数的位置上，则 $l = 1 , r = \dfrac{n - x}2 + 1$ , 而 $\operatorname{check}$ 函数就是查找当前 $x \sim \operatorname{mid}$ 的 $\gcd$ ，但是,由于 $\operatorname{mid}$ 表示第几个 $\operatorname{len}$ 长度为奇数的位置，而不是真正的位置，需要计算出 $\operatorname{truemid}= (\operatorname{mid} - 1) \times 2 + x$ ，接下来就是如何对 $l,r$ 进行变化。

• 若 $x \sim \operatorname{mid}$ 的 $\gcd$ 值正好等于 $3$ ，则记录答案，$l=\operatorname{mid} + 1$ 。

• 若 $x \sim \operatorname{mid}$ 的 $\gcd$ 值是 $3$ 的倍数且不等于 $3$ ，则 $l = \operatorname{mid} + 1$ 。

• 否则，$r = \operatorname{mid} - 1$ 。

这样子就能求出 $R$ 了。

其实很多人以为对于 $x \le k \le R$ , 其 $\gcd$ 的值都为 $3$ ，那就大错特错了，其实其 $\gcd$ 的值是 $3$ 的倍数，而不是 $3$ ，举个例子：

3
6 6 3

其中, 对于 $x=1$ 时 , $R=3$ ，但 $k=2$ 时，其 $\gcd$ 值为 $6$ ，不符合要求。

所以说还是要求 $L$ ，不过这也很简单，其实跟求 $R$ 是一样的，就是把范围缩小到了 $x \sim R$ 而已，这里就不过多阐述。

最后求出 $L$ 和 $R$ 后，就要计算答案了，这里可用求和公式计算。

其中首项为 $L - x + 1$ ，尾项为 $R-x + 1$ ，项数为 $\dfrac{R-L} 2 +1$，则局部答案为 $\dfrac{(L+R-2 \times x + 2) \times (\dfrac{R-L} 2 +1)} 2$。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int st[600010][30] , a[600010] , lg[600010];
void Init(int n){
    lg[1] = 0;
    for(int i = 2 ; i <= n ; i++) lg[i] = lg[i >> 1] + 1;
    for(int i = 1 ; i <= n ; i++) st[i][0] = a[i];
    for(int j = 1 ; j <= lg[n] ; j++){
        for(int i = 1 ; i + (1 << j) - 1 <= n ; i++) st[i][j] = __gcd(st[i + (1 << (j - 1))][j - 1] , st[i][j - 1]);
    }
}
int Find(int l , int r){
    int x = lg[r - l + 1];
    return __gcd(st[l][x] , st[r - (1 << x) + 1][x]);
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    Init(n);
    long long res = 0;
    for(int i = 1 ; i <= n ; i++){
        int l = 1 , r = (n - i) / 2 + 1;
        int best = -1;
        while(l <= r){
			int mid = (l + r) / 2;
			int true_mid = (mid - 1) * 2 + i;
			if(Find(i , true_mid) % 3 != 0) r = mid - 1;
			else if(Find(i , true_mid) % 3 == 0){
				best = max(best , true_mid);
				l = mid + 1;
			}
			else{
				l = mid + 1;
			}
		}
		int best2 = 1e9;
		if(best != -1){
			int l = 1 , r = (best - i) / 2 + 1;
			while(l <= r){
				int mid = (l + r) / 2;
				int true_mid = (mid - 1) * 2 + i;
				if(Find(i , true_mid) == 3){
					best2 = min(best2 , true_mid);
					r = mid - 1;
				}
				else l = mid + 1;
			}
			
		}
		if(!(best == -1 || best2 == 1e9)) res += (long long)(best + best2 - 2 * i + 2) * (long long)((best - best2) / 2 + 1) / 2ll;
		l = 1 , r = (n - i + 1) / 2;
        best = -1;
        while(l <= r){
			int mid = (l + r) / 2;
			int true_mid = mid * 2 + i - 1;
			if(Find(i , true_mid) % 2 != 0) r = mid - 1;
			else if(Find(i , true_mid) % 2 == 0){
				best = max(best , true_mid);
				l = mid + 1;
			}
			else{
				l = mid + 1;
			}
		}
		best2 = 1e9;
		if(best != -1){
			int l = 1 , r = (best - i + 1) / 2;
			while(l <= r){
				int mid = (l + r) / 2;
				int true_mid = mid * 2 + i - 1;
				if(Find(i , true_mid) == 2){
					best2 = min(best2 , true_mid);
					r = mid - 1;
				}
				else l = mid + 1;
			}		
		}
		if(best == -1 || best2 == 1e9) continue;	
		res += (long long)(best + best2 - 2 * i + 2) * (long long)((best - best2) / 2 + 1) / 2ll;
    }
    printf("%lld" , res);
    return 0;
}

如有错误，请予以指正。

（可能作者脑抽，没想到简单解法，有简单解法可以私信）