Author: lllyouo
Date: 20250702
tag: 同余
link: https://www.luogu.com.cn/problem/P1154

问题描述

link

分析

由同余的性质 $a\equiv b(\mathrm{mod}m)$ 当且仅当 $m\mid (a-b)$ 可知 $K$ 一定满足不是任意两个 $s_i$ 的差的倍数。

参考代码

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

const int N = 1e6 + 10;
int n, v[N], a[5010];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            v[abs(a[i] - a[j])] = 1;
        }
    }

    for (int i = n; i < N; i++) {
        if (!v[i]) {
            int flag = 1;
            for (int j = i; j < N; j += i) {
                if (v[j]) {
                    flag = 0;
                    break;
                }
            }

            if (!flag) continue;
            cout << i << endl;
            return 0;
        }
    }

    return 0;
}