CF763C Timofey and Remoduling

题目戳这里。

这道题目纯粹是考思维。
若(2N le M)，由于答案肯定是(s,s+d,dots,s+(N-1)d)，我们任意枚举两个数(a,b)，不妨设(b)在数列中出现在(a)后面(k)位，设(g = b-a)，则(g)这个差在所有数出现刚好(N-K)次。我们任取个(g)，用二分或哈希求个差出现次数，就可以得知(k)了，然后(d = gk^{-1})。在检验数列中有(a)的公差为(d)的等差数列是否存在即可。

若(2N > M)，我们考虑这些数的补集即可，这样就可以求出(d)了。

然后为什么(2N > M)不能用第一种情况来做呢？因为(kd)这个差不一定出现(N-k)次。因为假设我枚举到的差是((N-1)d)，那么(s+(2N-2)d)这个数有可能在模(M)意义下是在数列中的，但是这个数字又是不合法的。

程序实现还有一些细节，可以参考一下代码。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;

typedef long long ll;
const int maxn = 100010;
int M,N,A[maxn],B[maxn],ans1,ans2;

inline int gi()
{
	char ch; int ret = 0,f = 1;
	do ch = getchar(); while (!(ch >= '0'&&ch <= '9')&&ch != '-');
	if (ch == '-') f = -1,ch = getchar();
	do ret = ret*10+ch-'0',ch = getchar(); while (ch >= '0'&&ch <= '9');
	return ret*f;
}

inline ll qsm(ll a,int b)
{
	ll ret = 1;
	for (;b;b >>= 1,(a *= a) %= M) if (b&1) (ret *= a) %= M;
	return ret;
}

inline bool find(int *a,int n,int x) { return a[lower_bound(a+1,a+n+1,x)-a] == x; }

inline void solve(int *a,int n)
{
	if (n == 1) { ans1 = a[1],ans2 = 1; return; }
	int tmp = a[2]-a[1],cnt = 0,tot = 1;
	for (int i = 1;i <= n;++i) cnt += find(a,n,(a[i]+tmp)%M);
	ans2 = qsm(n-cnt,M-2)*tmp%M;
	for (int now = a[1],nx;;now = nx,++tot)
	{
		nx = now+ans2; if (nx >= M) nx -= M;
		if (!find(a,n,nx)) break;
	}
	for (int now = a[1],nx;;now = nx,++tot)
	{
		ans1 = now; nx = now-ans2; if (nx < 0) nx += M;
		if (!find(a,n,nx)) break;
	}
	if (tot != n) ans1 = -1; 
}

int main()
{
	freopen("763C.in","r",stdin);
	freopen("763C.out","w",stdout);
	M = gi(); N = gi();
	for (int i = 1;i <= N;++i) A[i] = gi();
	sort(A+1,A+N+1);
	if (N == 1||N == M) printf("%d 1
",A[1]);
	else
	{
		if (2*N <= M) solve(A,N);
		else
		{
			int n = 0;
			for (int i = 0;i < M;++i) if (!find(A,N,i)) B[++n] = i;
			solve(B,n);
			if (ans1 != -1) { ans1 += (ll)n*ans2%M; if (ans1 >= M) ans1 -= M; }
		}
		if (ans1 == -1) puts("-1");
		else printf("%d %d
",ans1,ans2);
	}
	fclose(stdin); fclose(stdout);
	return 0;
}