Product of numbers P44833


Statement
 

pdf   zip

html

Given a set of n natural numbers, choose any subset S such that ∏xS ≡ 1 (mod n ).

Input

Input consists of several cases. Every case begins with n, followed by n different numbers, all between 1 and 109. Assume 2 ≤ n ≤ 105.

It is easy to see that no number x where gcd(x, n) ≠ 1 could ever be part of any solution. Consequently, every given x is such that gcd(x, n) = 1.

Output

Print one line for every case, with a non-empty subset of the given numbers such that the product of its elements is congruent with 1 modulo n. Each number can be used at most once. Print the numbers in any order, and separated by one space. If there are several solutions, print any of them. If there is no solution, print “Maths are difficult”.

Public test cases
  • Input

    5  9 8 2 6 4
    5  9 8 2 6 4
    2  1 3
    4  10000003 10000007 10000011 10000015
    5  23 18 3 8 13
    

    Output

    8 2
    9 8 6 4 2
    3
    10000003 10000007
    23 18 3 8
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Desè Concurs de Programació de la UPC - Final
    Date
    2012-09-15