我无法解决与素数幂模 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)

输出：
一组 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

从素数乘积的限制来看，这个问题的作者不会喜欢这个解决方案，但是哦，好吧。

\n

令 U 为单位 mod 10 ⁹ + 7。从空散列\n映射开始，交替

\n

\n

1. 对均匀随机 (x ₁ , ..., x _{n\xe2\x88\x921} ) \xe2\x88\x88\nU ^{n\xe2\x88\x921}进行采样，并将其与\nx ₁ ^{p ₁} + ... + \nx _{n\xe2\x88\x921} ^{p _{n\xe2\x88\x921}} mod 10 ⁹ + 7 在哈希映射中，

   \n
\n

2. 对均匀随机 x _n \xe2\x88\x88 U 进行采样，并将其与哈希映射中的\nx _n ^{p _n} mod 10 ^{9 + 7 相关联，}

   \n
\n

\n

直到我们得到类型 1 的样本和类型 2 的样本之间的碰撞，表示有解决方案。

\n

根据生日悖论，该解决方案的预期复杂度约为素数模数的平方根，这应该足够快。

\n

好吧，从技术上讲，密钥不是统一随机的，原因有以下三个：

\n

\n

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

   \n
\n

2. 由于我们无法对零进行采样，所以存在一些轻微的失真。\n可以忽略不计。

   \n
\n

3. 真正的问题是两个素数让我们胃痛，即\n10 ⁹ + 6 的因数，即 2 和 500000003。素数 2\n 不是一个问题，因为它将我们折叠成二次余数，但\n这可能会增加一个常数因子。500000003 是一个真正的熊，因为\n我们只得到 \xc2\xb11 mod 10 ⁹ + 7。为了处理它，我们需要\n两个素数的 (1, 1) 解，并打乱方程\n以保留 500000003术语与另一个很好的随机性来源有关。

   \n
\n

\n

import random\n\nM = 10 ** 9 + 7\n\n\ndef solve(p, constant=0):\n    if len(p) == 2:\n        return [1, 1]\n    elif p[-1] == (M - 1) // 2:\n        # handle me by rearranging the equation\n        assert False\n    lhs_dict = {}\n    rhs_dict = {}\n    while True:\n        x = [random.randrange(1, M) for i in range(len(p))]\n        x_to_the_p = list(map(lambda xi, pi: pow(xi, pi, M), x, p))\n        lhs = sum(x_to_the_p[:-1]) % M\n        rhs = x_to_the_p[-1]\n        if lhs in rhs_dict:\n            return x[:-1] + rhs_dict[lhs]\n        lhs_dict[lhs] = x[:-1]\n        if rhs in lhs_dict:\n            return lhs_dict[rhs] + x[-1:]\n        rhs_dict[rhs] = x[-1:]\n\n\nprint(solve([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]))\n

\n