【 Codeforces Round #395 (Div. 2) E】Timofey and remoduling【数学思维题 —— 等差/等比数列】

题意：

有n个不同的数字， 给定$m$m，$m$m为质数。问是否能够用这$n$n个数字构造出一个模m意义下的等差数列，如果可以，请给出首项和公差。$(2\leq m\leq 10^9+7,1\leq n\leq 10^5)$(2≤m≤109+7,1≤n≤105)

思路：

比赛时没有思路，赛后参考了quality的解法。

首先先介绍等差数列求和公式和平方项求和公式。

然后可以发现，因为我们可以预先求出$S_n$Sn​与$S_n^2$Sn2​，因此只要能够确定出公差$d$d，我们就可以求出首项$a_1$a1​。因此我们需要枚举公差$d$d，首先将所有$a_i$ai​排序。对于$a_1$a1​来说，$a_2-a_n$a2​−an​中一定有一个数最后与$a_1$a1​相邻，因此我们枚举所有$a_i,i\in [2,n]$ai​,i∈[2,n]，令$d=a_i-a_1$d=ai​−a1​，然后求出公差为$d$d时，首项为多少。然后再将求出的$d$d与$a_1$a1​带入二次项公式进行检验 (这是一步剪枝操作)，如果与二次项结果相同，则再根据现在的$d$d与$a_1$a1​求出新的数组$b[i]$b[i]，与$a[i]$a[i]一一比对，比对正确后输出结果。若最后也没找到正确结果，则输出$-1$−1。

可以发现此处$S_n^2$Sn2​的主要目的是剪枝，剪枝完后即可去掉大量情况，最终可以通过此题。

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(ll i = a; i <= b; i++)
#define LOG1(x1,x2) cout << x1 << ": " << x2 << endl;
#define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl;
#define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl;
typedef long long ll;
typedef double db;
const int N = 1e5+100;
const int M = 1e5+100;
const db EPS = 1e-9;
using namespace std;

ll n,m,a[N],b[N];

ll powe(ll a,ll b,ll p)
{
	ll ans = 1;
	ll base = a;
	while(b)
	{
		if(b&1) ans = (ans*base)%p;
		b >>= 1;
		base = (base*base)%p;
	}
	return (ans%p);
}

int main()
{
	scanf("%lld%lld",&m,&n);
	rep(i,1,n) scanf("%lld",&a[i]);
	if(n == 1) printf("%lld 0\n",a[1]);
	else{
		sort(a+1,a+1+n);
		ll sum1 = 0, sum2 = 0;
		rep(i,1,n) sum1 = (sum1+a[i])%m, sum2 = (sum2+a[i]*a[i]%m)%m;
		// LOG2("sum1",sum1,"sum2",sum2);
		rep(i,2,n){
			ll d = a[i]-a[1];
			ll xx = (sum1*powe(n,m-2,m)%m-(n-1)*d%m*powe(2,m-2,m)%m+m)%m;
			ll yy = ((n*xx%m)*xx%m+n*(n-1ll)%m*(2*n-1ll)%m*powe(6,m-2,m)%m*d%m*d%m+n*(n-1)%m*d%m*xx%m)%m;
			// LOG3("d",d,"xx",xx,"yy",yy);
			if(yy == sum2){
				b[1] = xx;
				rep(i,2,n) b[i] = (b[i-1]+d)%m;
				sort(b+1,b+1+n);
				int jud = 0;
				rep(i,1,n)
					if(a[i] != b[i]){jud=1;break;}
				if(!jud){
					printf("%lld %lld\n",xx,d);
					return 0;
				}
			}
		}
		printf("-1\n");
	}
	return 0;
}