CF1355F

一个有点乱搞感觉的做法。

直接讲结论：每次取出最小的若干个乘积 $<10^{18}$ 的质数相乘询问，每次如果问出 $p\mid x$ 就再问一次判断有几个 $p$ 的因子，更新当前 $ans$ 和剩下因数乘积的上界 $lim$。如果全部询问用完就输出 $\left\lfloor\dfrac{9\times ans}{2}\right\rfloor$，如果枚举到的质数 $p^3>\lim$ 就输出 $ans\times 2$。

先讲后一种回答为什么是对的：在这种情况下，$\ge p$ 的质数对答案的贡献最多是 $\times 4$，最少是 $\times 1$，则输出 $ans\times 2$ 一定两倍范围内。

第一种回答就要复杂一点，其满足的是 $|ans-d|\le 7$ 这种情况。容易发现，我们一定是可以将 $\sqrt[4]{10^9}$ 内的质数问完的（只需要 $5$ 次），所以真实答案一定在 $[ans,ans\times 8]$ 的范围内。于是我们就需要保证回答时 $ans\le 2$。

此时发现若 $ans>2$，$\sqrt[3]{lim}\le630$，$\le 630$ 的质数需要 $16$ 次问完，也就是说这种情况会直接用第二种回答！如果 $lim$ 再变小，虽然可能前面需要的询问也会变多，但是毛估估一下 $lim$ 下降的很快，所以是可以保证 $ans>2$ 时全部都是用第二种回答的。

后来又想到，其实 $ans=2$ 时似乎也可以只用第二种回答？因为 $\sqrt[3]{5\times10^8}<800$ 只用 $20$ 次，加上前面问 $2$ 的幂次的 $1$ 次也是够的，更大就更不用说了。不过 $ans=1$ 的情况也是要用第一种处理的。

code：

int n,m;
vector<int> g;
bool isPrime(int x){
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			return 0;
		}
	}
	return 1;
}
il ll ask(int op,ll x){
	if(op==1){
		printf("! %lld\n",x);
		fflush(stdout);
		return 0;
	}
	printf("? %lld\n",x);
	fflush(stdout);
	ll ret;scanf("%lld",&ret);
	return ret;
}
void Yorushika(){
	m=1e9;int cnt=0,ans=1;ll sum=1;
	const ll mx=1e18;
	g.clear();
	rep(i,2,1000){
		if(isPrime(i)){
			if(sum>mx/i){
				ll x=ask(0,sum);
				cnt++;
				if(cnt==22){
					ask(1,ans*9/2);
					return;
				}
				for(int j:g){
					if(x%j==0){
						ll y=j;
						while(y<1e9){
							y*=j;
						}
						ll x=ask(0,y),z=0;
						m=m/x+1;
						while(x>1){
							x/=j,z++;
						}
						ans*=(z+1);
						if(++cnt==22){
							ask(1,ans*9/2);
							return;
						}
					}
				}
				if(1ll*i*i*i>m){
					ask(1,ans*2);
					return;
				}
				sum=i,g.clear(),g.eb(i);
			}else{
				sum*=i,g.eb(i);
			}
		}
	}
}
signed main(){
	int t=1;
		scanf("%d",&t);
	while(t--)
		Yorushika();
}