papyrus 喜欢谜题... 来解一道如何？

在你面前有一个被加密了的数组，其原数组是一个等差序列，你面前的则是将原数组中的所有数字都对m 取模再打乱后而得到的新数组

papyrus 给你出的谜题就是还原出原等差序列a

保证数据有解，而且因为papyrus 喜欢质数，所以他给你出的谜题中的m 一定是质数

今天题目还挺好玩的，虽然第二题因为数据太多OJ最后挂了全场爆0

但是还是把第一题切到了80分，后面卡卡常数就过去了

题意:给出一个模意义下的等差序列叫你求原序列

方法非常之多：有对称法，平方法，暴力枚举(雾)

我是用的是枚举+数论法

我们发现首项f一定在序列中，假设我们知道了首项那么就会有

nf+dn(n-1)/2=S (Mod m){S=Σai}

移项得到 n(n-1)d=2(S-nf) (Mod m)

这样就可以用一个扩展gcd求一下线性模方程就好了

让后考虑求出来的d是否合法

我当时考虑是使用随机选一些i并判断(id+f)%m是否在a中，如果是就接受这个答案

但是这样是有问题的，我被一个很强的数据卡了

没办法只好改为暴力枚举每一个i

但是这样似乎是可行的，因为很多情况下，可以直接break，再加上把set换成lowerbound就可以卡过

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define LL long longusing namespace std;LL exgcd(LL a,LL b,LL& x,LL& y){ if(b){ LL r=exgcd(b,a%b,y,x); y-=x*(a/b); return r; } else { x=1; y=0; return a; }}LL mod(LL a,LL b,LL p){ LL x,y,r=exgcd(a,p,x,y); x=(x+p)%p; return x*(b/r);}LL inv(LL a,LL p){ LL x,y,r=exgcd(a,p,x,y); return (x+p)%p;}LL in;int n,s[100010],p,b=0;int cal(LL f){ LL x,y,r=exgcd(n*(n-1ll)%p*in%p,p,x,y); return (x*((b-f*n%p+p)%p)%p+p)%p;}bool ok(LL d,int f){ for(int i=1;i
          
           >1))&&mxd>d&&ok(d,s[i])) if(d