题意：交互，有一个10次多项式，你可以询问50次当x为某个取值时多项式的值。你需要回答这个多项式的零点。
解：询问11个数然后高斯消元解方程得出系数。然后枚举定义域看有无0点。
1 #include2 3 const int N = 20, MO = 1000003; 4 5 int a[N][N], n = 10; 6 7 inline int qpow(int a, int b) { 8 int ans = 1; 9 while(b) {10 if(b & 1) {11 ans = 1ll * ans * a % MO;12 }13 a = 1ll * a * a % MO;14 b = b >> 1;15 }16 return ans;17 }18 19 inline void Gauss() {20 for(int i = 0; i < n; i++) {21 for(int j = i + 1; j <= n; j++) {22 if(a[j][i]) {23 std::swap(a[j], a[i]);24 break;25 }26 }27 if(!a[i][i]) continue;28 int inv = qpow(a[i][i], MO - 2);29 for(int j = i + 1; j <= n; j++) {30 if(!a[j][i]) continue;31 int p = 1ll * a[j][i] * inv % MO;32 for(int k = i; k <= n + 1; k++) {33 a[j][k] -= 1ll * a[i][k] * p % MO;34 a[j][k] = (a[j][k] % MO + MO) % MO;35 }36 }37 }38 for(int i = n; i > 0; i--) {39 a[i][n + 1] = 1ll * a[i][n + 1] * qpow(a[i][i], MO - 2) % MO;40 a[i][i] = 1;41 for(int j = i - 1; j >= 0; j--) {42 if(!a[j][i]) continue;43 int p = a[j][i];44 a[j][i] -= p;45 a[j][n + 1] -= 1ll * a[i][n + 1] * p % MO;46 a[j][n + 1] = (a[j][n + 1] % MO + MO) % MO;47 a[j][i] = (a[j][i] % MO + MO) % MO;48 }49 }50 return;51 }52 53 inline int cal(int x) {54 int ans = 0, temp = 1;55 for(int i = 0; i <= n; i++) {56 (ans += 1ll * temp * a[i][n + 1] % MO) %= MO;57 temp = 1ll * temp * x % MO;58 }59 return ans;60 }61 62 int main() {63 64 for(int i = 0; i <= n; i++) {65 fflush(stdout);66 printf("? %d \n", i);67 fflush(stdout);68 scanf("%d", &a[i][n + 1]);69 fflush(stdout);70 a[i][0] = 1;71 for(int j = 1; j <= n; j++) {72 a[i][j] = 1ll * a[i][j - 1] * i % MO;73 }74 }75 76 Gauss();77 78 int ans = -1;79 for(int i = 0; i < MO; i++) {80 if(!cal(i)) {81 ans = i;82 break;83 }84 }85 printf("! %d \n", ans);86 return 0;87 }