题解 P1154 【奶牛分厩】

· · 题解

这道题无非是倒推hash公式 Si mod k，让K成立，

不过既然是倒推，就不能用正推的方法

注意！！！枚举K不是最好的方法！！！！！

倒推要比正推好！

从另一个角度想，余数都不一样，就是证明没有一样的，

所以，

中国剩余定理满足这个要求！！！

（如果中国剩余定理（同余定理）不懂的童鞋要查一查了，这里不做多解释）

然后k不在辗转相减（同余定理的公式）的范围内，见缝插针！输出答案K。

但是数据很垃圾（说实话），上面这种方法差一点点，全对（数据严格的话）

可以清理K的倍数达到效果。

算法不深奥，附上骗分100算法

var
  n,m,i,j,k:longint;
  a,b:array[1..10000] of longint;
  c:array[0..1000000] of longint;
begin
  readln(n);
  for i:=1 to n do
    readln(a[i]);
  for i:=1 to n do
    for j:=i+1 to n do
    begin
      b[i]:=abs(a[i]-a[j]);//同余公式
      inc(c[b[i]]);
    end;
  for k:=n to 1000000 do//非暴力不合作
  if c[k]=0 then
  begin
    writeln(k);//骗分妙招：见缝插针
    halt;
  end;
end.