I can't solve a problem that related to prime power modulo 1e9+7. I think to solve this problem , we must use Constructive Algorithm

Question

Find x1, x2, ..., xn:
x_1^p_1 + x_2^p_2 + ... + x_(n-1)^p_(n-1) ≡ x_n^p_n (mod 1e9+7)

Input:
Line 1: Positive integer n > 1
Line 2: n distinct prime numbers p1, p2, ..., pn (p1 * p2 * ... * pn <= 1e18)

Output:
1 set of n positive integers (x_1, x_2,..., xn) (1 <= x_i < 1e9+7)

For example,

Input 1:
2
3 5

Output 1:
1 1
(Because 1^3 ≡ 1^5 (mod 10^9 + 7))

Input 2:
3
2 3 7

Output 2:
8 4 2
(Because 8^2 + 4^3 ≡ 2^7 (mod 10^9 + 7))

If n = 2, (1,1) is always satisfied. If n > 2, I think we can use Constructive Algorithm, but up to now, I have no idea

Answer 1

Judging by the restriction on the product of the primes, the author of this problem is not going to like this solution, but oh well.

Let U be the units mod 10⁹ + 7. Starting with an empty hash map, alternately

1. Sample a uniform random (x₁, ..., x_n−1) ∈ Uⁿ⁻¹ and associate it with x₁^p₁ + ... + x_n−1^p_n−1 mod 10⁹ + 7 in the hash map,

2. Sample a uniform random x_n ∈ U and associate it with x_n^p_n mod 10⁹ + 7 in the hash map,

until we get a collision between a sample of type 1 and a sample of type 2, signifying a solution.

According to the birthday paradox, the expected complexity of this solution is on the order of the square root of the prime modulus, which should be fast enough.

OK technically the keys aren't uniform random, for three reasons:

1. We're going to be using pseudorandom numbers. This won't be an issue in practice.

2. There's some slight distortion because we can't sample zero. Negligible.

3. The real issue is that two primes cause us heartburn, namely the factors of 10⁹ + 6, that is, 2 and 500000003. The prime 2 is less of an issue since it collapses us to quadratic residues, but that maybe adds a constant factor. 500000003 is a real bear because we only get ±1 mod 10⁹ + 7. To deal with it, we need the cheesy (1, 1) solution for two primes, and to shuffle the equation to keep the 500000003 term on the side with another good source of randomness.

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]))