P15032 棋子

LG086 · 2026-01-25 19:13:54 · 题解

从初始位置 m 开始，每次只能移动 k 个单位。问 k 是多少时可以经过给出的 n 个点，求出最大的 k。

从 m 开始，沿某一方向移动 a 次，可以到达的位置是 m+ak 或 m-ak。我们要保证每个点的位置 c_i 都满足 c_i = m+ak，则 c_i-m = ak，则 (c_i-m) \bmod k = 0，所以所有 c_i-m 都应该是 k 的倍数，所以说 k 是所有 c_i-m 的公约数，最大的 k 就是所有 c_i-m 的最大公约数。

注意，有负数的情况下，最大公约数计算结果可能为负。所以取个绝对值，求出 n 个 |c_i-m| 的最大公约数就行了。

:::info[示例代码]

区间求最大公约数，采用线段树实现。

仅供参考。

void build(int k,int l,int r){
 if(l==r){s3[k]=c[l];return;}
 build(ls,l,mid);build(rs,mid+1,r);
 s3[k]=gcd(s3[ls],s3[rs]);
}ll query(int k,int l,int r,int x,int y){
 if(x<=l and r<=y)return s3[k];
 if(y<=mid)return query(ls,l,mid,x,y);else if(x>=mid+1)return query(rs,mid+1,r,x,y);
 else return gcd(query(ls,l,mid,x,y),query(rs,mid+1,r,x,y));
}
int main(){
 read(n,m);
 for(int i=1;i<=n;++i)read(c[i]),c[i]-=m,c[i]=abs(c[i]);
 build(1,1,n);
 write(query(1,1,n,1,n));
}

:::