【2022 noip 模拟赛 14】A. 取模 做题记录

给定 $n$ 个整数 $a_1,a_2,\dots,a_n$，你可以选择两个 $\ge 2$ 的正整数 $x,y$，然后将每一个 $a_i$ 对 $x,y$ 之中某一个取模得到 $b_i$。

求 $b_i$ 中最少有多少种不同的数值。

$1\le n\le 2\times 10^5$

$1\le a_i\le 10^9$

首先答案肯定要么是 $1$ 要么是 $2$，因为我们可以对 $2$ 取模。

若已经知道了两个通过取模同一个数 $x$ 来得到 $b_i$ 的 $v1,v2$，那么就可以知道 $x|(|v1-v2|)$。而若取三个数 $v1,v2,v3$，则至少有两个数是通过取模同一个数来得到 $b_i$ 的。

所以只需要选出极差最小且两两不同的三个数，枚举它们两两的差值的因子做 $x$，检验是否合法即可。

检验某个 $x$ 的时间复杂度是 $O(n+\log V)$ 的，所以时间复杂度是 $O(3f(\lfloor\frac{V}{n}\rfloor)(n+logV))$，其中 $f(x)$ 表示 $[1,x]$ 内正整数的因子个数的最大值。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

#define fio(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout);

const int S=200005;

int n,a[S];

inline int gcd(int x,int y)
{
	if(x==0||y==0) return x+y;
	int t=x%y;
	while(t!=0) x=y,y=t,t=x%y;
	return y;
}

inline bool chk2(int val,int x)
{
	if(x==1) return false;
	int rt=0,y=0;
	for(int i=1;i<=n&&(y==0||(y>val&&y!=1));i++)
	{
		if(a[i]%x!=val)
		{
			if(a[i]<val) return false;
			y=gcd(y,a[i]-val);
		}
	}
	return y==0||(y>val&&y!=1);
}

inline bool chk(int val,int x)
{
	if(x<2) return false; 
	for(int d=1;d*d<=x;d++)
	{
		if(x%d==0)
		{
			if(chk2(val%d,d)) return true;
			if(d*d!=x&&chk2(val%(x/d),x/d)) return true;
		}
	}
	return false;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	n=unique(a+1,a+n+1)-a-1;
	if(n<=2) return puts("1"),0;
	int mn=0;
	for(int i=3;i<=n;i++) if(mn==0||a[i]-a[i-2]<a[mn]-a[mn-2]) mn=i;
	puts(
	chk(a[mn],a[mn]-a[mn-1])||
	chk(a[mn],a[mn]-a[mn-2])||
	chk(a[mn-1],a[mn-1]-a[mn-2])
	?"1":"2");
	return 0;
}