F - Guess Divisors Count
gyh20
2020-05-17 11:23:59
交互题？限制这么松？乱搞？
先讲一下做法，然后给证明。
枚举每一个质数，幂次初始为 $1$ ，加入优先队列，以幂次降序为第一关键字，质数大小升序为第二关键字，每次从队首取出，询问这些幂次的乘积，越大越好，如果包含这个幂次则令这个幂次 $+1$ 重新加入队列否则不加入，执行 $22$ 次，最后输出答案 $\times 2$。
证明？
$1.$操作在 $22$ 以内。
说得很清楚，执行 $22$ 次。
$2.$时间复杂度？
$22$ 次，每次选十几个，再加上最初加几万个到优先队列，但只有 $100$ 组数据，没问题。
$3.$正确性？
首先，一般情况下，这个程序能用到的最大质数大概在 $900$ 左右（不信你自己试），那么我们默认 $850$ 以下的质因子都搞定了（这个绝对不过分）。
那么剩下的情况：
$(1)~~1$，最终答案只多乘了 $2$，没有问题。
$(2)~$ 质数，最终答案乘了 $2$，刚好。
$(3)~$ 质数的平方，答案应该乘 $3$，但只乘了 $2$，差距没问题。
$(4)~$ 质数乘质数，应该乘 $4$，少乘了 $2$，没问题。
$(5)~$ 三个质数相乘，但我们发现，如果是三个 $850$ 以上质数相乘那不可能有其他质因子（$\times 2$ 就大于 $10^9$ 了），那么答案至多为 $8$，然而我们输出的 $2$ 也在可接受范围之内。
所以这样是正确的。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
inline int read() {
re int t=0;
re char v=getchar();
while(v<'0')v=getchar();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
return t;
}
int n,m,t,ans,p[40002],tot,a[40002];
bool ip[40002];
long long ss;
struct node{
int x,y,z;
bool operator <(const node a)const{
return a.y==y?a.x<x:a.y>y;
}
}b[40002];
priority_queue<node>q;
inline int gcd(re int x,re int y){
return y?gcd(y,x%y):x;
}
signed main() {
t=read();
n=4e4;
for (int i=2; i<=n; ++i) {
if (!ip[i])p[++tot]=i;
for(int j=1; j<=tot&&i*p[j]<=n; ++j) {
ip[i*p[j]]=1;
if(i/p[j]*p[j]==i)break;
}
}
while(t--){//re int kkk=read();
while(!q.empty())q.pop();ans=1;
for(re int i=1;i<=tot;++i)q.push((node){p[i],1,p[i]});
for(re int jj=1;jj<=22;++jj){
re int x=1,cnt=0;
while(!q.empty()){
node tmp=q.top();q.pop();
if(1.0*x*tmp.x>1e18){q.push(tmp);break;}
b[++cnt]=tmp,x*=tmp.x;
}
printf("? %lld\n",x);
fflush(stdout);
ss=read();
for(re int i=1;i<=cnt;++i){
if(ss%b[i].x==0){
ans/=b[i].y;
++b[i].y;
ans*=b[i].y;
b[i].x*=b[i].z;
q.push(b[i]);
}
}
}
printf("! %lld\n",ans*2);
fflush(stdout);
}
}
```