Numbers with no forbidden prefixes P83364


Statement
 

pdf   zip

thehtml

Write a backtracking program to print all the n-digit numbers such that none of its prefixes (the whole number included) is a multiple of any of m given forbidden divisors d1, …, dm.

For instance, if n = 3, m = 6 and the forbidden divisors are 2, 3, 5, 7, 11 and 19, then 137 is allowed, because none of its three prefixes 1, 13 and 137 is a multiple of any di. By contrast, 433 is not allowed, because some of its three prefixes 4, 43 and 433 is multiple os some di (4 ‍is multiple of 2).

Input

Input consists of several cases. Each case begins with n and m, followed by m different integer numbers between 2 and 1000. You can assume 1 ≤ n ≤ 9 and 1 ≤ m ≤ 15.

Output

For every case, print all the numbers with exactly n digits and no forbidden prefixes, one per line and in increasing order. Print a line with 10 dashes at the end of each case.

Public test cases
  • Input

    3 6
    2 3 5 7 11 19
    1 1
    2
    2 6
    3 4 7 11 12 13
    2 9
    2 3 5 7 9 11 13 17 19
    9 10
    199 191 193 17 13 11 7 5 3 2
    

    Output

    131
    137
    139
    173
    179
    ----------
    1
    3
    5
    7
    9
    ----------
    10
    17
    19
    23
    25
    29
    50
    53
    58
    59
    ----------
    ----------
    197399999
    197933933
    197933993
    197933999
    ----------
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++