#include <bits/stdc++.h>
const int N =
20, MO =
1000003;
int a[N][N], n =
10;
inline int qpow(
int a,
int b) {
int ans =
1;
while(b) {
if(b &
1) {
ans = 1ll * ans * a %
MO;
}
a = 1ll * a * a %
MO;
b = b >>
1;
}
return ans;
}
inline void Gauss() {
for(
int i =
0; i < n; i++
) {
for(
int j = i +
1; j <= n; j++
) {
if(a[j][i]) {
std::swap(a[j], a[i]);
break;
}
}
if(!a[i][i])
continue;
int inv = qpow(a[i][i], MO -
2);
for(
int j = i +
1; j <= n; j++
) {
if(!a[j][i])
continue;
int p = 1ll * a[j][i] * inv %
MO;
for(
int k = i; k <= n +
1; k++
) {
a[j][k] -= 1ll * a[i][k] * p %
MO;
a[j][k] = (a[j][k] % MO + MO) %
MO;
}
}
}
for(
int i = n; i >
0; i--
) {
a[i][n +
1] = 1ll * a[i][n +
1] * qpow(a[i][i], MO -
2) %
MO;
a[i][i] =
1;
for(
int j = i -
1; j >=
0; j--
) {
if(!a[j][i])
continue;
int p =
a[j][i];
a[j][i] -=
p;
a[j][n +
1] -= 1ll * a[i][n +
1] * p %
MO;
a[j][n +
1] = (a[j][n +
1] % MO + MO) %
MO;
a[j][i] = (a[j][i] % MO + MO) %
MO;
}
}
return;
}
inline int cal(
int x) {
int ans =
0, temp =
1;
for(
int i =
0; i <= n; i++
) {
(ans += 1ll * temp * a[i][n +
1] % MO) %=
MO;
temp = 1ll * temp * x %
MO;
}
return ans;
}
int main() {
for(
int i =
0; i <= n; i++
) {
fflush(stdout);
printf("? %d \n", i);
fflush(stdout);
scanf("%d", &a[i][n +
1]);
fflush(stdout);
a[i][0] =
1;
for(
int j =
1; j <= n; j++
) {
a[i][j] = 1ll * a[i][j -
1] * i %
MO;
}
}
Gauss();
int ans = -
1;
for(
int i =
0; i < MO; i++
) {
if(!
cal(i)) {
ans =
i;
break;
}
}
printf("! %d \n", ans);
return 0;
}
转载于:https://www.cnblogs.com/zsben991126/p/10793341.html
相关资源：三种消元法（全主元、Gauss消去法、列主元）
