题解 P10699 【[SNCPC2024] 猜质数 I】

Leasier · 2024-07-06 19:27:23 · 题解

为什么洛谷同步赛场上只有一个人过啊 /ng

显然 g(x) = (x - 1) \bmod 9 + 1。

注意到交互所能给我们的信息相当有限：顶天了就是 p \bmod 9。因此从原根等质数幂的性质角度出发是不可取的。这也告诉我们 k 没用。

注意到 n \leq 50，猜想可以构造 a_i \sim O(2^i)。

令 a_i = 2^i, m = 36 = 2^2 \times 9，则现在我们需要求 q^{2^i} \bmod 2^{i + 2}，随后与询问出的 q \bmod 9 的值 CRT 合并即可。

注意到 \forall i \in \mathbb{N}^*, \operatorname{ord}(2^{i + 2}) = 2^i，于是前者始终为 1。至此问题得解。

• 实际做这题的时候，我一开始尝试令 a_i = 2^{i - 1}，但由于 \operatorname{ord}(4) = 2 \neq 1，这样并不可行。

代码：

#include <stdio.h>

typedef long long ll;
typedef __int128 lll;

const int N = 50;
ll x[N + 7], y[N + 7], mod[N + 7], ans[N + 7];

inline ll quick_pow(ll x, ll p, ll mod){
    ll ans = 1;
    while (p){
        if (p & 1) ans = (lll)ans * x % mod;
        x = (lll)x * x % mod;
        p >>= 1;
    }
    return ans;
}

int main(){
    int t;
    scanf("%d", &t);
    for (int i = 1; i <= N; i++){
        ll a = 1ll << (i + 2);
        x[i] = a * quick_pow(a, 5, 9);
        y[i] = 9 * quick_pow(9, a / 2 - 1, a);
        mod[i] = 9 * a;
    }
    for (int i = 1; i <= t; i++){
        int n, k;
        scanf("%d %d", &n, &k);
        for (int j = 1; j <= n; j++){
            int r;
            printf("%lld\n", 1ll << j);
            fflush(stdout);
            scanf("%d", &r);
            ans[j] = (x[j] * r + y[j]) % mod[j];
        }
        printf("36\n");
        for (int j = 1; j <= n; j++){
            printf("%lld ", ans[j]);
        }
        printf("\n");
        fflush(stdout);
    }
    return 0;
}