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

user_16077632 0
Viewed 1071

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

primes algorithm
1 Answers

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 109 + 7. Starting with an empty hash map, alternately

  1. Sample a uniform random (x1, ..., xn−1) ∈ Un−1 and associate it with x1p1 + ... + xn−1pn−1 mod 109 + 7 in the hash map,

  2. Sample a uniform random xn ∈ U and associate it with xnpn mod 109 + 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 109 + 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 109 + 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]))
user_21446690
Related