CF1355F Guess Divisors Count 题解

题意：

要求猜一个 $1$ 到 $10^9$ 之间的一个数 $X$。

你可以询问一个数 $Q$（$1\le Q\le10^{18}$），然后得到 $\gcd(X,Q)$。

请你在不多于 $22$ 次询问后算出 $X$ 的因数个数。

注意：设你的答案为 $d$，标准答案为 $r$，只要满足 $|r-d|\le7$ 或 $\frac12\le\frac{r}{d}\le2$ 即算正确。

输入格式：

首先输入一个正整数，数据组数 $t(1\le t \le 100)$。

接下来 $t$ 组数据。

交互格式：

询问：? Q；

回答：! d。（注意每次输出后要刷新缓冲区）。

本题特色：乱搞？

感觉很多这种类型的题就和快慢刀一样，主打一个迷惑人，其实本质没有那么难。

首先，根据唯一分解定理可知若 $X = \prod_{i=1}^n p_i^{x_i}$ ，则因数个数为 $\prod_{i=1}^n\left(x_i+1\right)$ 。

因此不考虑询问个数，大量询问各个质数和质数的幂即可猜出答案。

但是可以预见的是，很多时候得到的答案都是 $1$ ，本题要求我们优化这个询问的思路。

那么，如果我们一口气询问多个质数的乘积，是否更可能获得答案呢？

于是我们试图维护一个由质数组成的集合，每次取出若干元素取出并相乘（要求乘积不超过 $10^{18}$ ）

在询问后我们可以立即得到哪些质数有用，哪些不再有用，并将有用的那些质数的次数加 $1$ 再塞进去。

于是我们需要将所有的质数按次幂降序为第一关键字，质数大小为第二关键字排序，这可以用优先队列维护。

考虑仅执行 $22$ 次询问，根据实验可发现通常至多询问到 $900$ 左右。

此时我们其实已经得到了一个模糊的答案，下面证明这个答案恰好满足题目的奇怪条件。

显然 $850$ 以下的所有质因子我们都已经搞定了，对于 $X$ 的其余情况：

$1$ ，没有问题
质数，答案需要乘以 $2$ （乘法原理）
质数的平方，答案需要乘以 $3$
质数乘质数，答案需要乘以 $4$
三个质数相乘。因为三个质因子都大于 $850$ ，所以实际上不会有其他质因子了，此时的答案为 $8$

有意思的是，如果我们把输出的答案乘以 $2$ ，上面的所有情况都满足了题目的限制，~~真是神奇呐~~

时间复杂度 $\mathcal{O}(\mathrm{ok})$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(40000 + 15))

const int _ = 40000;
char ck[N]; int pcnt, p[N];
struct node { int x, y, z; } b[N];
bool operator<(node a, node b) { return a.y == b.y ? a.x > b.x : a.y < b.y; }
priority_queue<node> q;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
void solve()
{
    int res = 1; while(!q.empty()) q.pop();
    for(int i = 1; i <= pcnt; i++) q.push({p[i], 1, p[i]});
    for(int t = 1; t <= 22; t++)
    {
        int x = 1, cnt = 0;
        while(!q.empty()) {
            auto tmp = q.top(); q.pop();
            if(1.0 * tmp.x * x > 1e18) { q.push(tmp); break; }
            b[++cnt] = tmp; x *= tmp.x;
        }
        cout << "? " << x << '\n'; cout.flush();
        int g; cin >> g;
        for(int i = 1; i <= cnt; i++)
            if(g % b[i].x == 0) {
                res /= b[i].y; ++b[i].y; res *= b[i].y;
                b[i].x *= b[i].z; q.push(b[i]);
            }
    }
    cout << "! " << res * 2 << '\n'; cout.flush();
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    for(int i = 2; i <= _; i++)
    {
        if(!ck[i]) p[++pcnt] = i;
        for(int j = 1; j <= pcnt && i * p[j] <= _; j++) {
            ck[i * p[j]] = true; if(i % p[j] == 0) break;
        }
    }
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}