自动搬运

查看原文

来自洛谷，原作者为

	Leasier 我们所知的是沧海一粟，我们所不知的是汪洋大海。

搬运于2025-08-24 23:00:23，当前版本为作者最后更新于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;
}