GYM101408D-Disgruntled Judge(枚举加

传送门

题意：

给出满足等式的n个数字，需要输出满足等式的n个数。

思路：

找出了x1与x3的关系。于是建立欧几里得关系。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,c,x,y,gcd;
ll x1,x5,x3;
ll sum[10010];
int n;
const int mod=10001;
void exgcd(ll a,ll b,ll &gcd,ll &x,ll &y)
{
  if(b==0)
  {
      gcd=a;
      x=1;
      y=0;
  }
  else
  {
      exgcd(b,a%b,gcd,y,x);
      y-=x*(a/b);
  }
}
int main( )
{
  cin>>n;
  for(int i=1;i<=n;i++)
  {
      cin>>sum[i];
  }
  x1=sum[1];
  x3=sum[2];
  x5=sum[3];
  ll flaga,flagb,flag;
  for(int i=0;i<=10000;i++)
  {
      flag=0;
      a=i+1;
      b=mod;
      c=x3-i*i*x1;
      exgcd(a,b,gcd,x,y);
      //cout<<gcd<<" gcd "<<endl;
      x=x*c;
      ll t=b;
      if(x>=0)
      {
          x=x%t;
      }
      else
      {
          x=x%t+t;
      }
      flaga=i;
      flagb=x;
      for(int i=2;i<=n;i++)
      {
          ll res=(flaga*flaga*sum[i-1]+(flaga+1)*flagb)%mod;
          if(res!=sum[i])
          {
              flag=1;
              break;
          }
      }
      if(flag==0)
      {
          break;
      }
      
  }
  // cout<<flaga<<" a "<<endl;
  // cout<<flagb<<" b "<<endl;
  for(int i=1;i<=n;i++)
  {
      cout<<(flaga*sum[i]+flagb)%mod<<endl;
  }
  return 0;
}