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） 題意：是否有一個等差數(shù)列x,x+d,..,x+(n-1)*d，使得其每個元素對m取模后，結(jié)果為a1,a2,..,an。如果有，輸出首項x和公差d。如果沒有，輸出-1。多解輸出一個即可。 題解：我們通過枚舉d和a1,來驗證所求隊列是否滿足題意. 這里用到兩個等差隊列數(shù)學公式: 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函數(shù)的作用. 代碼：
#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");}新聞熱點
疑難解答
