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;
}