E. Timofey and remoduling----數論及數學公式

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 integersx, 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      

題目連結：http://codeforces.com/contest/764/problem/E

題目的意思是是否有一個等差數列x,x+d...,x+(n-1)*d,使得其每個元素對m取模後，結果為a1,a2,...,an。如果有，輸出首項x和公差d。如果沒有，則輸出-1,。多解輸出一個即可。

cf的div2的第五題，比賽的時候我都沒有看到這個題，賽後看了看這個題，發現比賽的時候 看了也是白看，完全沒有思路，想了一會後，無奈，還是去搜了題解，本以為剛比完不會有大牛寫部落格，但是竟然有一篇，然後仔細研究了一個多小時，終于通了這個題，我的天。

先放上大牛的連結：http://blog.csdn.net/qq_33183401/article/details/54884972

大牛說是用的Q神的思路，Q神簡直了，作為大連賽區就坐在我後面的隊伍，表示我的壓力山大啊。

思路還算簡單，沒有繞彎，主要就是兩個數學公式的運用，然後去驗證題目中給出的序列即可，我用代碼詳細講。

兩個數學公式：

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 

膜一發我的Q。

代碼：

//a1=(sn-n*(n-1)/2*d)/n
//Sn^2=n(a1)^2+n(n-1)(2n-1)d^2/6+n(n-1)*d*a1  兩個數學公式的運用
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a[300000];//存放輸入取模後的序列
int s[2];//兩個數學公式的結果
int b[300000];//存放驗證取模後的序列
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);
    s[0]=s[1]=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\n",a[1]);
    }            
sort(a+1,a+n+1);
    for(int i=2;i<=n;i++){
        int d=(a[i]-a[1]+m)%m;//枚舉每一個d,這裡可以仔細想一下，意思其實就是肯定會有一個和a[1]在原序列中相鄰的1個數，那麼兩者做差就是d
        int x=1LL*(s[0]-1LL*n*(n-1)/2%m*d%m+m)%m*fp(n,m-2,m)%m;//枚舉每一個a1
        int ans=1LL*n*x%m*x%m;//第二個式子求和
        ans=(ans+1LL*n*(n-1)%m*d%m*x%m)%m;
        ans=(ans+1LL*n*(n-1)*(2*n-1)/6%m*d%m*d%m)%m;
        if(ans==s[1]){//當Sn^2相等時，驗證
            b[1]=x;
            for(int j=2;j<=n;j++){//構造自己取模後的序列
                b[j]=b[j-1]+d;
                b[j]%=m;
            }
            sort(b+1,b+n+1);
            bool flag=true;
            for(int j=1;j<=n;j++){//驗證
                if(a[j]!=b[j]){
                    flag=false;
                    break;
                }
            }
            if(flag){//輸出
                return 0*printf("%d %d\n",x,d);
            }
        }
    }
    return 0*printf("-1\n");
}
           
            
 跟着Q神又學了點東西，再次膜。