题意：告诉你存在一个未知项系数最高为10的$f(x)$，你最多可以有50次询问，每次询问给出一个$x'$，系统会返回你$f(x')$的值，你需要猜一个$x''$，使得$f(x'')=0$，所有运算都是取模1e6+3下进行的。
思路：拉格朗日插值法的模板题。yyb聚聚的公式
$p(x)=$\sum\limits_{n}^{i=0}$(-1)n-i*p(i)*x*(x-1)*(x-2)*(x-3)*……*(x-n)/((n-i)! * i! * (x-i))$
所以先暴力询问0-10的所有答案，然后判断11-p的答案是否为0即可。
#include<bits/stdc++.h>
#define CLR(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const ll p=1e6+;
ll a[],f[],jcinv[],inv[p+];
ll qpow(ll a,ll b){
ll res=;
a%=p;
while(b){
if(b&)res=res*a%p;
b>>=;
a=a*a%p;
}
return res;
}
void init(){
f[]=;
for(int i=;i<=;i++)f[i]=f[i-]*i%p;
jcinv[]=qpow(f[],p-);
for(int i=;i>;i--){
jcinv[i-]=jcinv[i]*i%p;
}
inv[]=;
for(int i=;i<=p;i++)
{
inv[i]=inv[p%i]*(p-p/i)%p;
}
}
int main(){
init();
for(int i=;i<=;i++)
{
printf("? %d\n",i);
fflush(stdout);
scanf("%lld",&a[i]);
if(a[i]==){
printf("! %d\n",i);
fflush(stdout);
return ;
}
}
for(int k=;k<p;k++)
{
ll up=;
for(int i=;i<=;i++)up=up*(k-i)%p;
ll res=;
for(int i=;i<=;i++)
{
ll tep=;
tep=a[i]*up%p*jcinv[-i]%p*jcinv[i]%p*inv[k-i]%p;
res=(res+tep*(i%==?:-)+p)%p;
}
if(res==){
printf("! %d\n",k);
fflush(stdout);
return ;
}
}
printf("! -1\n");
fflush(stdout);
}