CF1155E Guess the Root 题解

目录

• 题目链接
• sol

题目链接

cf1155E

sol

思路

众所周知，n个点可以确定一个n-1次多项式，所以我们问11次就可确定这个多项式。问11次后可以高斯消元或拉格朗日插值，之后暴力带入0到1e6-3之间的数检验。

可能会有分数，需要逆元，使用拉格朗日插值会更简单。

code

#include<bits/stdc++.h>
using namespace std;
const int mod=1e6+3;
inline int powmod(int a,int b) {
	int ans=1;
	while(b) {
		if(b&1)ans=1ll*ans*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return ans;
}
int p[11];
int qry(int a) {//交互询问
	printf("? %d
",a);fflush(stdout);
	int t;
	cin>>t;
	return t;
}
void write(int i) {//交互输出
	printf("! %d
",i);fflush(stdout);
	exit(0);
}
int main() {
	for(int i=0;i<=10;i++) {//先问11次
		p[i]=qry(i);
		if(!p[i])write(i);
		for(int j=0;j<=10;j++) {
			if(i==j)continue;
			p[i]=1ll*p[i]*powmod(i-j,mod-2)%mod;//拉格朗日插值，顺便考虑逆元。
		}
	}
	for(int i=11;i<mod;i++) {//暴力代入
		int v=0;
		for(int j=0;j<=10;j++) {
			int val=1;
			for(int k=0;k<=10;k++) {
				if(j==k)continue;
				val=1ll*val*(i-k)%mod;
			}
			v=(v+1ll*val*p[j])%mod;
		}
		if(v==0)write(i);
	}
	write(-1);
	return 0;
}