传送门
题意：
给出满足等式的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;
}
