CF1155E Guess the Root

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题意：交互，有一个10次多项式，你可以询问50次当x为某个取值时多项式的值。你需要回答这个多项式的零点。

解：询问11个数然后高斯消元解方程得出系数。然后枚举定义域看有无0点。

#include <bits/stdc++.h> const int N = , MO = ; int a[N][N], n = ; inline int qpow(int a, int b) {
int ans = ;
while(b) {
if(b & ) {
ans = 1ll * ans * a % MO;
}
a = 1ll * a * a % MO;
b = b >> ;
}
return ans;
} inline void Gauss() {
for(int i = ; i < n; i++) {
for(int j = i + ; 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 - );
for(int j = i + ; j <= n; j++) {
if(!a[j][i]) continue;
int p = 1ll * a[j][i] * inv % MO;
for(int k = i; k <= n + ; k++) {
a[j][k] -= 1ll * a[i][k] * p % MO;
a[j][k] = (a[j][k] % MO + MO) % MO;
}
}
}
for(int i = n; i > ; i--) {
a[i][n + ] = 1ll * a[i][n + ] * qpow(a[i][i], MO - ) % MO;
a[i][i] = ;
for(int j = i - ; j >= ; j--) {
if(!a[j][i]) continue;
int p = a[j][i];
a[j][i] -= p;
a[j][n + ] -= 1ll * a[i][n + ] * p % MO;
a[j][n + ] = (a[j][n + ] % MO + MO) % MO;
a[j][i] = (a[j][i] % MO + MO) % MO;
}
}
return;
} inline int cal(int x) {
int ans = , temp = ;
for(int i = ; i <= n; i++) {
(ans += 1ll * temp * a[i][n + ] % MO) %= MO;
temp = 1ll * temp * x % MO;
}
return ans;
} int main() { for(int i = ; i <= n; i++) {
fflush(stdout);
printf("? %d \n", i);
fflush(stdout);
scanf("%d", &a[i][n + ]);
fflush(stdout);
a[i][] = ;
for(int j = ; j <= n; j++) {
a[i][j] = 1ll * a[i][j - ] * i % MO;
}
} Gauss(); int ans = -;
for(int i = ; i < MO; i++) {
if(!cal(i)) {
ans = i;
break;
}
}
printf("! %d \n", ans);
return ;
}