【Educational Codeforces Round 63?E. Guess the Root】交互+高斯消元

链接

Educational Codeforces Round 63?E. Guess the Root

题意

现在有$11$个数，$a_0,a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9,a_{10}$,$0\le a_i\le 10^6+2$
他们组成一个函数$f_x=a_0+a_1\times x+a_2\times x^2+...a_k\times x^k$，
现在你可以给出$50$个询问，系统会返回$f_{x}mod(10^6+3)$.
在$50$次询问之后，你要给出一个$x$,使$f_x\equiv 0\mathrm{m}\mathrm{o}\mathrm{d}(10^6+3)$.

做法

给出不同的11个x可以得到11个方程，现在有11个方程11个未知数，高斯消元求解即可。

求解之后得到$a_0,a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9,a_{10}$,由于答案要求的范围是$[0,1e6+2]$。

我们只需要枚举并检验$f_x\equiv 0\mathrm{m}\mathrm{o}\mathrm{d}(10^6+3)$,由于这个不消耗询问次数，所以在11次询问后就可以确定答案。

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<map>
#include<bitset>
#include<stack>
#include<set>
#include<vector>
#include <time.h>
#include<string.h>
using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;const int maxn = 20;
const int Mod=1000003;
const int p = 1000003;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double e=exp(1);
const db PI = acos(-1);
const db ERR = 1e-10;#define Se second
#define Fi first
#define pb push_back
#define ok cout<<"OK"<<endl
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl
ll a[maxn][maxn];  //增广矩阵
ll x[maxn];        //解集
ll pow_(ll a,ll b)
{
    ll ans=1;while(b){
    if(b&1) ans=ans*a%Mod;b>>=1;a=a*a%Mod;}return ans;
}
int n=11;
void gauss()
{
    for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++)if(i!=j){
    long long tmp=a[i][i]*pow_(a[j][i],p-2)%p;for(int k=1;k<=n+1;k++) a[j][k]=a[i][k]-a[j][k]*tmp%p,a[j][k]=((a[j][k]%p)+p)%p;}}for(int i=1;i<=n;i++){
    a[i][n+1]*=pow_(a[i][i],p-2),a[i][n+1]%=p;x[i]=a[i][n+1];}}
int main()
{
    for(int i=1;i<=n;i++){
    printf("? %d\n",i);fflush(stdout);int ans;scanf("%d",&ans);a[i][12]=ans;a[i][1]=1;for(int j=2;j<=n;j++) a[i][j]=1LL*a[i][j-1]*i%Mod;}gauss();int flag=0;for(int i=0;i<Mod;i++){
    ll tt=0;for(int j=1;j<=11;j++){
    tt=(tt+x[j]*pow_(i,j-1)%Mod)%Mod;}if(tt==0){
    flag=1;printf("! %d\n",i);fflush(stdout);break;}}if(flag==0){
    printf("! -1\n");fflush(stdout);}return 0;
}