千仓平丰歉

【题目简述】

有 $n$ 个数 $c_i$。每次可以选择一个位置，把它增加 $a$ 或 $b$。求任意次操作后，所有数极差的最小值。

【数据点 1∼41\sim41∼4】

【题目描述】

当 $n$ 很小时，可以枚举最终所有数落入的区间，并逐个判断每个 $c_i$ 能否通过若干次加 $a$、加 $b$ 落入其中。

【Hint】

加法操作不会改变 $\gcd(a,b)$ 的余数。这个不变量比原数值更重要。

【解法】

令 $d=\gcd(a,b)$。每个 $c_i$ 在任意操作后模 $d$ 的余数不变。反过来，由裴蜀定理，足够大的同余位置都可以由 $c_i$ 经过若干次操作到达。因此这一档已经说明：只需考虑余数在模环上的相对位置。

【正解】

【题目描述】

令 $r_i=c_i\bmod d$。现在要求在长度为 $d$ 的环上找到最短的一段连续弧，覆盖全部 $r_i$。

【Hint】

与其直接找被覆盖部分，不如找哪一段空隙不经过。

【解法】

将余数排序为 $r_1\le r_2\le\cdots\le r_n$。所有未出现余数形成的空隙中，最大的一个长度为

选择这段最大空隙不经过，剩下的短弧恰好覆盖所有余数，所以答案为

这也给出了构造：把每个数抬高到该短弧中与其同余的位置即可。

【复杂度分析】

排序一次，时间复杂度为 $\mathcal{O}(n\log n)$，空间复杂度为 $\mathcal{O}(n)$。

【参考代码】

1#include <cstdio>2#include <algorithm>3#define MAXN 1000104using namespace std;5int T,n,a,b,c[MAXN];6int Gcd(int x,int y){7    return y?Gcd(y,x%y):x;8}9void Solve(){10    scanf("%d%d%d",&n,&a,&b);11    int d=Gcd(a,b);12    for(int i=1;i<=n;i++) scanf("%d",&c[i]),c[i]%=d;13    sort(c+1,c+n+1);14    int Max=c[1]+d-c[n];15    for(int i=2;i<=n;i++) Max=max(Max,c[i]-c[i-1]);16    printf("%d\n",d-Max);17}18int main(){19    scanf("%d",&T);20    while(T-->0) Solve();21    return 0;22}