Codeforces ECR #063 : E. Guess the Root

なんだこりゃ？
https://codeforces.com/contest/1155/problem/E

問題

あるK次の多項式f(x)がある。
各次数の係数は0以上(10^6+3)未満である。

xを指定すると、f(x) mod (10^6+3)を返すクエリを11回まで利用できるとする。
f(x) mod (10^6+3)が0となるxを求めよ。

解法

Kは10以下なので、11回クエリを投げればあとはガウス法で各係数を求めることができる。
あとはxを0～(10^6+2)まで総当たりしてf(x)の値を求めればよい。

const int MAT=50;
ll mo=1000003;
ll ma[50][50],V[50],R[50];
ll rev(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

int Gauss(int n,ll mat_[MAT][MAT],ll v_[MAT],ll r[MAT]) {
	int i,j,k;
	ll mat[MAT][MAT],v[MAT];
	memmove(mat,mat_,sizeof(mat));
	memmove(v,v_,sizeof(v));
	
	FOR(i,n) {
		if(mat[i][i]==0) {
			for(j=i+1;j<n;j++) if(mat[j][i]) break;
			if(j>=n) break;
			FOR(k,n) swap(mat[i][k],mat[j][k]);
			swap(v[i],v[j]);
		}
		(v[i]*=rev(mat[i][i]))%=mo;
		for(k=n-1;k>=i;k--) (mat[i][k]*=rev(mat[i][i]))%=mo;
		for(j=i+1;j<n;j++) {
			v[j]=((v[j]-v[i]*mat[j][i]%mo)+mo)%mo;
			for(k=n-1;k>=i;k--) mat[j][k]=((mat[j][k]-mat[i][k]*mat[j][i]%mo)+mo)%mo;
		}
	}
	
	for(i=n-1;i>=0;i--) {
		for(j=n-1;j>i;j--) v[i]=((v[i]-mat[i][j]*v[j]%mo)+mo)%mo;
		r[i]=v[i];
	}
	return n;
}

int A[11]={1,2,3,4,5,6,7,8,11,10};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,11) {
		cout<<"? "<<i<<endl;
		cin>>R[i];
		/*
		ll sum=0;
		FOR(j,11) sum+=A[j]*modpow(i,j);
		R[i]=sum%mo;
		cout<<R[i]<<endl;
		*/
		FOR(j,11) ma[i][j]=modpow(i,j);
	}
	
	x=Gauss(11,ma,R,V);
	
	FOR(i,mo) {
		ll sum=0;
		FOR(j,11) sum+=V[j]*modpow(i,j)%mo;
		sum%=mo;
		if(sum==0) {
			cout<<"! "<<i<<endl;
			return;
		}
	}
	cout<<"! -1"<<endl;
	
}

まとめ

いまいち何をさせたいかわからない問題。