P12239 [蓝桥杯 2023 国 Java A] 游戏的得分

· · 题解

思路：

若一个轮数 n 是合法的，当且仅当存在一个 i \in [0, n] 满足：

2^{n + i} \equiv a_i, 2^{2n - i} \equiv b_i

这是显然的。

于是你可以先 BSGS 求出最小的 x_0, y_0 满足 2^{x_0} \equiv a_i, 2^{y_0} \equiv b_i；那么所有可行的解 x, y 都可以表示为 x_0 + k_1 \delta_p(2), y_0 + k_2 \delta_p(2)；先跑一次 BSGS 可以得到 \delta_p(2) = \frac{p - 1}{2}。

问题变为在所有解 x, y 中，找到 x + y \equiv 0 \pmod 3 且 \frac{\max(x, y)}{\min(x, y)} \le 2 且 x + y 最小的解；发现这个限制模数很小，所以可以贪心的选择 x, y 最小的增加 \delta_p(2)；单次复杂度是 O(3^2 \cdot \log_p ans) = O(1) 的。

每次暴力 BSGS，时间复杂度为 O(T \sqrt p)，无法通过。

容易发现，问题是P11175 【模板】基于值域预处理的快速离散对数，使用模版题的做法，然后换底公式即可。

本题中没有那么必要开科技，考虑 BSGS 的本质的根号分治平衡，本题由于询问过多，考虑重新设置阈值 B：

时间复杂度是 O(\frac{\delta_2(p)}{B} + qB) \ge O(\sqrt{\delta_2(p) q})，取 B = \sqrt{\frac{\delta_2(p)}{q}} 即可。

完整代码：

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define lowbit(x) x & (-x)
#define pi pair<ll, ll>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
using namespace __gnu_pbds;
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int p = 998244353, d2 = (p - 1) >> 1, M = 105;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
            f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
int T, a, b, m, B;
int pow2[M];
gp_hash_table<int, int> mp;
inline int qpow(int a, int b){
    int ans = 1;
    while(b){
        if(b & 1)
            ans = 1ll * ans * a % p;
        a = 1ll * a * a % p;
        b >>= 1;
    }
    return ans;
}
inline void init(int a = 2){
    pow2[0] = 1;
    for(int i = 1; i <= B; ++i)
      pow2[i] = 2ll * pow2[i - 1] % p;
    m = d2 / B + 1;
//  cerr << m << '\n';
    int x = pow2[B], now = 1;
    for(int i = 1; i <= m; ++i){
        now = 1ll * now * x % p;
        if(mp.find(now) == mp.end())
          mp[now] = i;
    }
}
inline int solve(int b){
    if(b == 1)
      return 0;
    int ans = 1e9;
    for(int i = 0; i < B; ++i){
        int now = 1ll * b * pow2[i] % p;
        if(mp.find(now) != mp.end())
          ans = min(ans, mp[now] * B - i);
    }
    return ans == 1e9 ? -1 : ans;
}
inline void solve(){
    a = read(), b = read();
    ll x0 = solve(a), y0 = solve(b);
//  cerr << x0 << ' ' << y0 << '\n';
    if(x0 == -1 || y0 == -1){
        puts("-1");
        return ;
    }
    while(((x0 + y0) % 3 != 0) || !(max(x0, y0) <= 2ll * min(x0, y0))){
        if(x0 < y0)
          x0 += d2;
        else
          y0 += d2;
    }
//  cerr << x0 << ' ' << y0 << '\n';
    write((x0 + y0) / 3);
    putchar('\n');
//  cerr << (2ll * y0 - x0) / 3 << ' ' << (x0 + y0) / 3 - (2ll * y0 - x0) / 3 << '\n';
}
int main(){
//  freopen("A.in", "r", stdin);
    T = read();
//  B = sqrt(d2 / T);
    B = 80;
//  cerr << B << '\n';
    init(2);
    while(T--)
        solve();
    return 0;
}