题解：CF1482B Restore Modulo

Yuzih · 2026-05-07 18:26:08 · 题解

题目大意

给定一个长度为 n 的序列 a，判断是否存在非负整数 n,m,c,s（0\le c<m）满足：

若存在，在保证 m 最大的前提下输出 m 和 c；若 m 可以为任意大小，输出 0；若不存在，输出 -1。

分析

思路

考虑相邻两项的差值 d_i = a_i - a_{i-1}（2\le i\le n）。
由于 a_i 是由 a_{i-1} 加上 c 后对 m 取模得到的，整个加法和取模的过程中只会发生两种情况：

1. 相加后仍比 m 小（不会溢出）：a_{i-1}+c < m，此时 a_i = a_{i-1}+c， d_i = a_i - a_{i-1} = c（非负）；
2. 相加后比 m 大（会溢出）：a_{i-1}+c \ge m，此时 a_i = a_{i-1}+c-m， d_i = a_i - a_{i-1} = c-m（负数）。

因此，所有 d_i 的取值只能有两种：非负整数 p=c，或负整数 q=c-m。

分类讨论

遍历整个序列，求出最大值 M=\max a_i，同时记录所有不同的正差值（大于等于 0 的 d_i）与负差值（小于0的 d_i）。

• 若 n=1
  只要 m > a_1 即可，m 可以为任意大小，直接输出 0。

• 若差值种类超过 2（正差值不唯一或负差值不唯一）
  不可能由一个 c 生成，输出 -1。

• 若所有差值均相同（全为非负整数或全为负整数）
  如果全为非负整数，设差值为 p，只要让 c=p，这样每次加法都不会溢出，同时只要 m>M 就能满足题目要求；
  如果全为负整数，设负差值为 q，则只要 q=c-m，c= (c-m)+m=q+m\ge0，每次加法都会溢出（即符合题目要求），同时保证 m\ge-q 即可，因此 m 没有最大值。
  两种情况下 m 都可以为任意大小，输出 0。

• 若差值为一个非负整数 p 和一个负整数 q
  让 c=p，m=c-(c-m)=p-q，m>M即可满足要求。
  此外，还需验证每个位置的“溢出”行为是否与差值一致：

  • 对于 d_i = p\ge 0 的位置，必须不溢出（即 a_{i-1}+c < m）；
  • 对于 d_i = q < 0 的位置，必须溢出（即 a_{i-1}+c \ge m）。
    若全部满足，则 m 即为最大模数，输出 m 和 c，否则无解（输出 -1）。

为什么 m 一定最大

首先 m 不为 0 或 -1 时，只有既有正差 p 又有负差 q 的情况。此时 m 必须等于 p-q 才能让两个差值分别对应溢出与不溢出。如果将 m 增大，原本恰好溢出的位置将不再溢出，差值就会变成正数，与给定的序列矛盾。

参考代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=100010;

int t,n;
int a[MAXN];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        bool f=1;
        int p=-1,q=1,ma,c,m;
        cin>>n;
        for (int i=1;i<=n;i++) cin>>a[i];
        if (n==1){                         //n==1的情况，直接输出0。
            cout<<0<<endl;
            continue;
        }
        ma = a[1];
        for (int i=2;i<=n;i++){
            int d=a[i]-a[i-1];
            if (d>=0){
                if (p==-1) p = d;
                else if(p!=d) f=0;         //若前后正差不一样，输出-1（让f=false）。
            }
            else{
                if (q==1) q = d;
                else if(q!=d) f=0;        //若前后负差不一样，输出-1（让f=false）。
            }
            ma = max(ma,a[i]);            //取最大值ma。
        }
        if (!f){
            cout<<-1<<endl;
            continue;
        }
        if (p==-1||q==1){                 //若所有差值均相同（全为非负整数或全为负整数）的情况。
            cout<<0<<endl;
            continue;
        }
        c = p;
        m = p-q;
        if (m<=ma){                       //保证m大于最大值ma。
            cout<<-1<<endl;
            continue;
        }
        f = 1;                        
        for (int i=2;i<=n;i++){           //检查每个位置溢出情况是否同步。
            int d = a[i]-a[i-1];
            if (d>=0){                    //若差值（d）大于0则一定不能溢出。
                if (a[i-1]+c>=m){         //若会溢出则不能满足构造，输出-1。
                    f = 0;
                    break;
                }
            }
            else{                         //若差值（d）小于0则一定要溢出。
                if (a[i-1]+c<m){          //若无法溢出则不能满足构造，输出-1。
                    f = 0;
                    break;
                }
            }
        }
        if (f) cout<<m<<' '<<c<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}