goodbye 2020,hello 2021
[x] CF1355F
一道有意思的交互题。
简单思考后发现超过 $sqrt{10^9}$ 的质数我们不需要考虑他们的存在，只要让答案乘二即可。
而对于 $leq sqrt{10^9}$ 的质数，我们每次询问 $prod_i p_i$ ，$p_i$ 表示一个质数，我们就可以知道 $X$ 中是否存在这个质数。
而对于一个 $leq 10^9$ 的数，最多可以包含 $9$ 个质因子，那么我们最多需要 $5$ 次操作就可以问出 $X$ 中质数的幂。
但是注意到 $sqrt{10^9}$ 太多了，而很容易发现其实只需要保留 $leq sqrt[3]{10^9}$ 即可，因为我们允许的是最多剩下两个质数，只需输出 $2 imes Ans$ 即可，因为最后答有可能是 $Ans,2 imes Ans,3 imes Ans,4 imes Ans$ ，无论取哪个都符合条件。
则我们将值域缩到了 $1000$ ，交互次数还达不到 $22$ 次，然后就不会了。。。
可以发现我们少用了一个条件，$|Ans-real|leq 7$ 。 不难想到我们的值域还可以在减少一点！
我们将上述情况进行推导，我们设已知的质数乘积为 $x$ ，则当我们扫描的质数 $p$ 满足 $xcdot p^3>10^9$ 就可以停止。
如果说 $xgeq 4$ 时，我们只需要扫描 $leq sqrt[3]{frac{10^9}{4}}$ 的质数，交互次数为 $21$ 次，符合条件。
否则，当扫描前面的质数 $x<4$ 时，那么我们最多答案为 $16$ ，最小为 $1$ ，只需要输出 $8$ 即可。
那么我们只需要将 $2cdot Ans$ 与 $8$ 做比较，扫描前 $leq sqrt[3]{frac{10^9}{4}}$ 即可解决问题。
上限 $21$ 次即可解决问题，还是在将质数从小到大直接分组的情况下，应该还是有优化的空间的。
#include<iostream> #include<cstring> #include<cstdio> #include<cstring> #include<vector> #include<queue> #include<algorithm> #include<climits> #define int long long #define pii pair<int,int> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } const int MAXN=1e5+11; const int INF1=1e18; const int INF2=1e9; int v[MAXN],pri[MAXN]; void init(){ for(int i=2;i<MAXN;i++){ if(!v[i]) pri[++pri[0]]=i,v[i]=i; for(int j=1;pri[j]<MAXN/i;j++){ v[pri[j]*i]=pri[j]; if(!(i%pri[j])) break; } }return; } int gcd(int a,int b){return !b?a:gcd(b,a%b);} int ask(int x){printf("? %lld ",x);fflush(stdout);return read();} void tell(int x){printf("! %lld ",x);fflush(stdout);return;} vector<int> vec[21],ANS; int cnt,G[21]; signed main(){ init(); pri[0]=114; cnt=1; G[1]=1; for(int i=1;i<=pri[0];i++){ if(G[cnt]<=INF1/pri[i]){vec[cnt].pb(pri[i]);G[cnt]*=pri[i];continue;} ++cnt; vec[cnt].pb(pri[i]),G[cnt]=pri[i]; } int cas=read();while(cas--){ int Ans=1; ANS.clear(); for(int i=1;i<=cnt;i++){ int P=ask(G[i]); for(auto v:vec[i]) if(!(P%v)) ANS.pb(v); } for(int j=0;j+1<ANS.size();j+=2){ int p=ANS[j],q=ANS[j+1],r1=1,r2=1; while(r1<=INF2/p) r1*=p; while(r2<=INF2/q) r2*=q; int R=ask(r1*r2),c1=0,c2=0; while(!(R%p)) c1++,R/=p; while(!(R%q)) c2++,R/=q; Ans=Ans*(c1+1)*(c2+1); } if(ANS.size()&1){ int p=ANS[ANS.size()-1],r=1; while(r<=INF2/p) r*=p; int R=ask(r),c=0; while(!(R%p)) c++,R/=p; Ans=Ans*(c+1); } tell(max(8ll,Ans*2)); } }