E. Timofey and remoduling
time limit per test:2 seconds
memory limit per test:256 megabytes
input:standard input
output:standard output
Little Timofey likes integers a lot. Unfortunately, he is very young and can’t work with very big integers, so he does all the Operations modulo his favorite PRime m. Also, Timofey likes to look for arithmetical progressions everywhere.
One of his birthday presents was a sequence of distinct integers a1, a2, …, an. Timofey wants to know whether he can rearrange the elements of the sequence so that is will be an arithmetical progression modulo m, or not.
Arithmetical progression modulo m of length n with first element x and difference d is sequence of integers x, x + d, x + 2d, …, x + (n - 1)·d, each taken modulo m.
Input
The first line contains two integers m and n (2 ≤ m ≤ 109 + 7, 1 ≤ n ≤ 105, m is prime) — Timofey’s favorite prime module and the length of the sequence.
The second line contains n distinct integers a1, a2, …, an (0 ≤ ai < m) — the elements of the sequence.
Output
Print -1 if it is not possible to rearrange the elements of the sequence so that is will be an arithmetical progression modulo m.
Otherwise, print two integers — the first element of the obtained progression x (0 ≤ x < m) and its difference d (0 ≤ d < m).
If there are multiple answers, print any of them.
Examples
Input 17 5 0 2 4 13 15
Output 13 2
Input 17 5 0 2 4 13 14
Output -1
Input 5 3 1 2 3 Output 3 4 (思路代码参考quality） 题意：是否有一个等差数列x,x+d,..,x+(n-1)*d，使得其每个元素对m取模后，结果为a1,a2,..,an。如果有，输出首项x和公差d。如果没有，输出-1。多解输出一个即可。 题解：我们通过枚举d和a1,来验证所求队列是否满足题意. 这里用到两个等差队列数学公式: 1:a1=(sn-n*(n-1)/2*d)/n 2:Sn^2=n(a1)^2+n(n-1)(2n-1)d^2/6+n(n-1)*d*a1 在用第一个公式的时候因为涉及到除法取模,所以我们得求一下逆元(代码中fp函数的作用. 代码：
#include <bits/stdc++.h>using namespace std;const int MAXN=100005;int a[MAXN],b[MAXN];int fp(int a,int k,int m){ int res=1; while(k) { if(k&1)res=1LL*res*a%m; a=1LL*a*a%m; k>>=1; } return res;}int main(){ int m,n; scanf("%d%d",&m,&n); int s[2]={0,0}; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); s[0]=(s[0]+a[i])%m; s[1]=(s[1]+1LL*a[i]*a[i])%m; } if(n==1)return 0*printf("%d 0",a[1]); if(n==m)return 0*printf("0 1"); sort(a+1,a+n+1); for(int i=2;i<=n;i++) { int d=(a[i]-a[1]+m)%m; int x=1LL*(s[0]-1LL*n*(n-1)/2%m*d%m+m)*fp(n,m-2,m)%m;//a1=(sn-n*(n-1)/2*d)/n; //Sn=n(a1)^2+n(n-1)(2n-1)d^2/6+n(n-1)*d*a1 int tmp=1LL*n*x%m*x%m; tmp=(tmp+1LL*n*(n-1)%m*d%m*x%m)%m; tmp=(tmp+1LL*n*(n-1)*(2*n-1)/6%m*d%m*d%m)%m; if(tmp==s[1]) { b[1]=x; for(int i=2;i<=n;i++) b[i]=(b[i-1]+d)%m; sort(b+1,b+n+1); bool isok=1; for(int i=1;i<=n;i++) isok&=(a[i]==b[i]); if(isok)return 0*printf("%d %d",x,d); } } return 0*printf("-1");}新闻热点
疑难解答
