F. Maximum modulo equality 题解

核心考点：数论 + 区间GCD + ST表（稀疏表）

---

0. 一分钟读懂题目

给定数组 $a$，多组询问 $[l,r]$： 求最大的 $m$，使得

$$a_l \bmod m = a_{l+1} \bmod m = \dots = a_r \bmod m $$

• 若区间长度为 $1$（$l=r$），输出 $0$
• 否则输出最大满足条件的 $m$

---

1. 核心数学结论（解题关键）

结论

$a \bmod m = b \bmod m$ 的充要条件：

$$m \mid |a - b|$$

推广到整个区间： 所有数模 $m$ 相等 $\iff$ $m$ 能整除区间内所有相邻数的差值 $\iff$ $m$ 是这些差值的最大公约数（GCD）

最终结论

答案 = 区间 $[l, r-1]$ 上相邻差分数组的 GCD

---

2. 解题步骤

1. 构造差分数组 $s[i] = |a[i+1] - a[i]|$

2. 预处理 ST 表 支持区间GCD查询（$O(1)$ 每次查询）

3. 处理询问

   • $l=r$：输出 $0$
   • 否则查询 $\gcd(s[l\dots r-1])$ 并输出

---

3. 完整代码 + 逐行精讲

#include <bits/stdc++.h>
using namespace std;

int n,q,a[200005],s[200005];
int l,r,Log[200005];  // Log数组：快速查询log2值

// ST表：维护区间GCD
struct ST_map{
	int Gcd[200005][21];  // Gcd[i][j]：从i开始，长度2^j的区间GCD
	
	void Init(){
		// 初始化：长度为1的区间
		for(int i=1;i<=n-1;i++) Gcd[i][0]=s[i];
		
		// 预处理：2^1 ~ 2^20
		for(int i=1;i<=20;i++){
			for(int j=1;j<=n-1;j++){
				// 两段合并：2^(i-1) + 2^(i-1)
				Gcd[j][i] = __gcd(
					Gcd[j][i-1],
					Gcd[min(j+(1<<(i-1)), n)][i-1]
				);
			}
		}
	}
	
	// O(1)查询区间[l,r]的GCD
	int Query(int l,int r){
		int len = r - l + 1;
		int logx = Log[len];
		return __gcd(
			Gcd[l][logx],
			Gcd[r - (1<<logx) + 1][logx]
		);
	}
}ST;

void Main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	
	// 构建差分数组 s[i] = |a[i+1]-a[i]|
	for(int i=1;i<n;i++)
		s[i] = abs(a[i+1] - a[i]);
	
	ST.Init();  // 初始化ST表
	
	while(q--){
		scanf("%d%d",&l,&r);
		if(l == r) printf("0 ");        // 长度1，输出0
		else printf("%d ", ST.Query(l, r-1));  // 查询差分数组区间GCD
	}
	puts("");
} 

int T;
int main()
{
	// 预处理Log数组：Log[i] = floor(log2(i))
	int cnt=0, last=2;
	for(int i=2;i<=200000;i++){
		if(i == last){
			cnt++;
			last *= 2;
		}
		Log[i] = cnt;
	}
	
	scanf("%d",&T);
	while(T--) Main();
	return 0;
}

---

4. 关键细节说明

① 差分数组为什么是 $s[i] = |a[i+1]-a[i]|$

因为所有数模 $m$ 相等 $\iff$ 所有相邻差都能被 $m$ 整除 $\iff$ $m$ 是这些差的最大公约数

② 为什么用 ST 表

• 区间GCD满足可重复贡献
• ST表预处理 $O(n\log n)$，查询 $O(1)$
• 完美适配本题 $n,q \le 2\times10^5$ 的数据规模

③ 询问对应关系

原询问 $[l, r]$ $\rightarrow$ 对应差分数组 $[l, r-1]$ $\rightarrow$ 查询这个区间的GCD就是答案

---

5. 复杂度分析

• 预处理：$O(n\log n)$
• 单次查询：$O(1)$
• 总复杂度：$O(\sum n\log n + \sum q)$

完全可以轻松通过本题所有数据

---

6. 一句话总结

这道题就是披着模运算外衣的区间GCD模板题：

1. 转差分
2. 建ST表
3. 查区间GCD