【ybtoj高效進階 21286】等差數列（數學）（分類讨論）

等差數列

題目連結：ybtoj高效進階 21286

題目大意

給你一個數組 A，裡面元素互不相同，問你是否可以把它重排成一個數組 B，使得它在模 M 的意義下是等差序列。

隻需輸出首項和公差即可。

思路

首先發現 M M M 是質數，那就說明無論公差是什麼（反正他都是小于 M M M），那它在模 M M M 意義下的循環節一定是 M M M，也就是依次把 0 ∼ M − 1 0\sim M-1 0∼M−1 的數都周遊一遍。

考慮進行分類讨論，首先随便找到兩個數的差，那它肯定是可以用 K d Kd Kd 表示的。（ d d d 是公差， K K K 就是一個普通的整數）

如果 2 n ⩽ M 2n\leqslant M 2n⩽M，那就應該恰好有 K K K 個數字 x x x 是滿足 x + K d x+Kd x+Kd 是不在這個序列中的。那我們就可以得到 K K K 進而得到 d d d。

說明：那我們 + K d +Kd +Kd 就相當于跳到它等差序列後面 K K K 位，那如果它是一個等差序列，那 n − K + 1 ∼ n n-K+1\sim n n−K+1∼n 項加上之後就是空的，一共是 K K K 個。

但因為它是一個環狀，是以有限制條件是 2 n ⩽ M 2n\leqslant M 2n⩽M，這樣它就算是最後一個加了也不會轉一圈那麼多。

那接着就是 2 n > M 2n>M 2n>M，這個時候最後一個加了就會超過一圈了。

那似乎又變得很難搞了？

其實不，你想想不是數組中的那一半。

對，它也是等差序列啊，你可以求那個等差序列的答案，然後移一下首項就好啦！

接着考慮如何實作，用 STL 的 lower_bound 即可實作。

代碼

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long

using namespace std;

ll T, m, n, a[100001];
ll fir, b[100001], t, d;
bool in[100001];

ll ksm(ll x, ll y) {
	ll re = 1;
	while (y) {
		if (y & 1) re = re * x % m;
		x = x * x % m;
		y >>= 1;
	}
	return re;
}

void work(ll *a, ll n) {
	if (n == 1) {
		fir = a[1]; d = 1;
		return ;
	}
	
	ll kd = a[2] - a[1], k = 0;
	for (int i = 1; i <= n; i++) {
		if (a[lower_bound(a + 1, a + n + 1, (a[i] + kd) % m) - a] != (a[i] + kd) % m)
			k++;
	}
	
	d = kd * ksm(k, m - 2) % m; fir = -1;
	for (int i = 1; i <= n; i++) {
		if (a[lower_bound(a + 1, a + n + 1, (a[i] - d + m) % m) - a] != (a[i] - d + m) % m) {
			if (fir == -1) fir = a[i];
				else {
					fir = -1;
					return ;
				}
		}
	}
}

int main() {
//	freopen("sequence.in", "r", stdin);
//	freopen("sequence.out", "w", stdout);
	
	scanf("%d", &T);
	while (T--) {
		memset(in, 0, sizeof(in));
		
		scanf("%lld %lld", &m, &n);
		for (int i = 1; i <= n; i++) {
			scanf("%lld", &a[i]);
		}
		
		sort(a + 1, a + n + 1);
		
		ll kd = a[2] - a[1], k = 0;
		if (n * 2 <= m) {
			work(a, n);
		}
		else {
			t = 0;
			for (int i = 0; i < m; i++)
				if (a[lower_bound(a + 1, a + n + 1, i) - a] != i)
					b[++t] = i;
			work(b, t);
			if(fir != -1) {
				fir = (fir + d * t % m) % m;
			}
		}
		
		if (fir == -1) {
			printf("-1\n");
			continue;
		}
		printf("%lld %lld\n", fir, d);
	}
	
	return 0;
}