题解：CF1355F Guess Divisors Count

· · 题解

首先是 \frac{1}{2}≤ans/d≤2 这个限制，他告诉我们猜数 2x 可以将标准答案在 [x,4x] 中的情况全部覆盖。我们熟知，比 \sqrt{V_X} 大的因子最多只有 1 个，这个限制只能扩大到 2 倍，太松了。进一步的，比 \sqrt[3]{V_X}=\sqrt[3]{10^9}=10^3 大的质因子至多只有 2 个，最多凑到 {P_1}^1\times {P_2}^1 的形式得到 4 倍贡献，因此我们只需要求出只考虑 \le 10^3 的质因子时得出的标准答案 ans，输出 2\cdot ans 即可。

在只考虑小质因子时的交互方式比较容易想到，取 Q=2\times 3\times 5\times 7\times \dots \times P_1\le V_Q 进行一次询问可以得到这个质数集中有哪些质因子出现了，按 V_Q 的限制分段，一直分到所有 \le 10^3 的质数，写出来发现这样分有 25 组。得到所有质因子的集合之后，容易发现对质数 p 只需要 Q 中带一个足够大的 p^t 作为因子就可以得到 p 在 X 中的指数，对每个 p 可以取 p^{\lceil \log_p V_X\rceil}，将这些数在不爆 V_Q 上界的前提下尽可能凑起来一起问，同时在确定质因子的同时不断缩小 V_X 这个上界即可。但是这样仍然需要至少 25 次询问，不可行。

这个询问策略本身不太能优化了，故考虑将 10^3 这个上界进一步缩小。注意到 |ans-d|\le 7 这个限制还没用上。一个观察是 ans 已经有一定值的时候 X 的上界会缩小，能够凑出 ans>2 的最小数是 2^2，此时 X 的上界缩减到了 V_X/(2^2)，考虑取 B=\sqrt[3]{V_X/(2^2)}\approx 629，只考虑质因子 \le B 时得到的答案为 ans。

只考虑 \le 629 的质因子时实测询问最多只需要 22 次，可以通过。

:::success[代码]

#include <bits/stdc++.h>
#define bint __int128
#define psb push_back
#define DEBUG 1

using namespace std;

typedef long long ll;
const ll LIM = 1e18, MAX=1e9;
const int M = 629;
int primes[M+5],tot; bool st[M+5];
void get_primes()
{
    for (int i=2;i<=M;i++)
    {
        if (!st[i]) primes[++tot]=i;
        for (int j=1;primes[j] <= M/i;j++)
        {
            st[i*primes[j]]=true;
            if (i%primes[j]==0) break;
        }
    }
}

int getcnt(int x)
{
    int res=1;
    for (int i=2;i<=x/i;i++)
    {
        if (x%i==0)
        {
            int c=0;
            while (x%i==0) x/=i, c++;
            res=res*(c+1);
        }
    }
    if (x>1) res=res*2;
    return res;
}

ll X; int QCNT;
ll query(ll Q)
{
    if (DEBUG) return QCNT++, __gcd(X,Q);
    cout << "? " << Q << "\n"; fflush(stdout);
    ll res; cin >> res; return res;
}

void solve()
{
    if (DEBUG) cin >> X, QCNT=0, cout << "standard : " << getcnt(X) << "\n";
    vector<int> pr;
    for (int i=1;i<=tot;i++)
    {
        int j=i-1; ll prod=1;
        while (j<tot && (bint)prod*primes[j+1] <= LIM) j++, prod*=primes[j];
        //cout << i << " " << j << " " << prod << "\n"; 
        ll res=query(prod); for (int k=i;k<=j;k++) if (res % primes[k] == 0) pr.psb(primes[k]);  
        i=j;
    }
    //for (int x : pr) cout << x << " "; cout << "\n";
    int bound = MAX; ll cur = 1; int ans = 1;
    for (int i=0;i<pr.size();i++)
    {
        if (pr[i] > bound) break; 
        ll prod=pr[i]; while (prod*pr[i] <= bound) prod*=pr[i];
        //cout << pr[i] << " " << prod << "\n";
        if ((bint)cur * prod > LIM) { ll res=query(cur); bound /= res; ans *= getcnt(res); cur=prod; }
        else cur *= prod;
    }
    ans *= getcnt(query(cur));
    if (ans==1) cout << "! 8\n";
    else if (ans==2) cout << "! 9\n";
    else cout << "! " << ans*2 << "\n";
    fflush(stdout);

    if (DEBUG) cout << "Query " << QCNT << "\n";
}

int main()
{
    get_primes(); int T; cin >> T; while (T--) solve();
    return 0;
}

:::