CF2050F Maximum modulo equality 题解

Determination_Y · 2024-12-06 22:03:25 · 题解

Cnblogs

【题意简述】

你有一个长度为 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，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 同余可拆分成：

然后就出结论了，m=\gcd(\vert a_l-a_{l+1}\vert ,\vert a_{l+1}-a_{l+2}\vert ,…,\vert a_{r-2}-a_{r-1}\vert ,\vert a_{r-1}-a_r\vert )。

用 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。

两发罚时全是数组开小，乐。

以后就打不了了。