【题意简述】
你有一个长度为 \(n\) 的数组 \(a\)。
每一次询问给定 \(l,r\),寻找最大的 \(m\) 使得 \(a_l\) 到 \(a_r\) 的所有数对 \(m\) 同余,
【前置数学芝士】
首先是一个非常 Naive 的结论,请自行感性证明:设 \(a>b\),\(a\) 和 \(b\) 对 \(a-b\) 同余。
理性证明:
设 \(p=a-b\),\(a=kp+q\)
那么 \(b=a-(a-b)=a-p=(k-1)p+q\)
他们对 \(p\) 同余(都是 \(q\))
然后另一个非常 Naive 的结论,请自行感性证明:设 \(a>b\),\(a\) 和 \(b\) 对 \(a-b\) 的所有因数同余。
理性证明:
设 \(p=a-b\),\(a=kp+q\)\(p=a-b\),\(b=(k-1)p+q\)
设 \(p\) 的这个因数为 \(p_0\)
因为 \(kp\) 和 \((k-1)p\) 可以被 \(p\) 整除,所以这两个数也可以被 \(p_0\) 整除,同余于 \(p_0\)
而且 \(q\) 和 \(q\) 同余于 \(p_0\)
所以 \(a\) 和 \(b\) 的两部分分别同余于 \(p_0\)
所以 \(a\) 和 \(b\) 同余于 \(p_0\)
【思路】
首先 \(a_l\) 到 \(a_r\) 同余可拆分成:
限制 | 结论 |
---|---|
\(a_l,a_{l+1}\) 同余 | \(m\) 是 \(|a_l-a_{l+1}|\) 的因数 |
\(a_{l+1},a_{l+2}\) 同余 | \(m\) 是 \(|a_{l+1}-a_{l+2}|\) 的因数 |
\(…\) | \(…\) |
\(a_{r-2},a_{r-1}\) 同余 | \(m\) 是 \(|a_{r-2}-a_{r-1}|\) 的因数 |
\(a_{r-1},a_r\) 同余 | \(m\) 是 \(|a_{r-1}-a_r|\) 的因数 |
然后就出结论了,\(m=\gcd(|a_l-a_{l+1}|,|a_{l+1}-a_{l+2}|,…,|a_{r-2}-a_{r-1}|,|a_{r-1}-a_r|)\)。
用 ST 表搞一搞,特判一下区间长度为 1。
【Code】
#include <bits/stdc++.h>
using namespace std;
int n,q,a[200005],s[200005];
int l,r,Log[200005];
struct ST_map{
int Gcd[200005][21];
void Init(){
for(int i=1;i<=n-1;i++) Gcd[i][0]=s[i];
for(int i=1;i<=20;i++){
for(int j=1;j<=n-1;j++){
Gcd[j][i]=__gcd(Gcd[j][i-1],Gcd[min(j+(1<<(i-1)),n)][i-1]);
}
}
}
int Query(int l,int r){
int logx=Log[r-l+1];
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]);
for(int i=1;i<n;i++) s[i]=abs(a[i+1]-a[i]);
ST.Init();
while(q--){
scanf("%d%d",&l,&r);
if(l==r) printf("0 ");
else printf("%d ",ST.Query(l,r-1));
}puts("");
}
int T;
int main()
{
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;
}
【后记】
祝贺我自己,在上蓝前的最后一场 Div.3 AK。
两发罚时全是数组开小,乐。
以后就打不了了。
标签:equality,200005,int,题解,kp,因数,CF2050F,同余于,同余 From: https://www.cnblogs.com/Sundar-2022/p/18591483