algorithm - 我无法解决与素数幂模 1e9+7 相关的问题。我认为要解决这个问题，我们必须使用构造算法

Question

找到 x1, x2, ..., xn:
x_1^p_1 + x_2^p_2 + ... + x_(n-1)^p_(n-1) ≡ x_n^p_n (mod 1e9+7)
输入:
第 1 行:正整数 n > 1
第 2 行:n 个不同的素数 p1, p2, ..., pn (p1 * p2 * ... * pn <= 1e18)
输出:
1 组 n 个正整数 (x_1, x_2,..., xn) (1 <= x_i < 1e9+7)
例如，
输入 1:
2
3 5
输出 1:
1 1
(因为 1^3 ≡ 1^5 (mod 10^9 + 7))
输入 2:
3
2 3 7
输出 2:
8 4 2
(因为 8^2 + 4^3 ≡ 2^7 (mod 10^9 + 7))
如果 n = 2，则始终满足 (1,1)。
如果 n > 2，我认为我们可以使用构造算法，但到目前为止，我不知道

Answer 1

从素数乘积的限制来看，作者
这个问题不会喜欢这个解决方案，但是哦。
让 U 为单位 mod 109 + 7。从一个空哈希开始
map ，交替

采样一个均匀随机 (x1, ..., xn−1) ∈
Un−1 并将其与
x1p1 + ... +
xn−1pn−1 mod 109 + 7 in
哈希映射，

采样一个均匀随机 xn ∈ U 并将其与
xnpn mod 109 + 7
哈希映射，

直到我们在类型 1 的样本和类型的样本之间发生碰撞
2、表示解决。
根据生日悖论，这个的预期复杂性
解是质数模的平方根的数量级，即
应该足够快。
好吧，从技术上讲， key 不是统一随机的，原因有以下三个:

我们将使用伪随机数。这不会成为问题
在实践中。

有一些轻微的失真，因为我们不能采样零。
微不足道。

真正的问题是有两个素数会引起我们的胃灼热，即
109 + 6 的因数，即 2 和 500000003。素数 2
不是什么问题，因为它使我们崩溃到二次残差，但是
这可能会增加一个常数因子。 500000003 是一只真正的熊，因为
我们只得到±1 mod 109 + 7。为了处理它，我们需要
两个素数的俗气 (1, 1) 解，并打乱方程
将 500000003 术语保留在另一个好的来源
随机性。

import random

M = 10 ** 9 + 7


def solve(p, constant=0):
    if len(p) == 2:
        return [1, 1]
    elif p[-1] == (M - 1) // 2:
        # handle me by rearranging the equation
        assert False
    lhs_dict = {}
    rhs_dict = {}
    while True:
        x = [random.randrange(1, M) for i in range(len(p))]
        x_to_the_p = list(map(lambda xi, pi: pow(xi, pi, M), x, p))
        lhs = sum(x_to_the_p[:-1]) % M
        rhs = x_to_the_p[-1]
        if lhs in rhs_dict:
            return x[:-1] + rhs_dict[lhs]
        lhs_dict[lhs] = x[:-1]
        if rhs in lhs_dict:
            return lhs_dict[rhs] + x[-1:]
        rhs_dict[rhs] = x[-1:]


print(solve([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]))