Numbers with no forbidden prefixes P83364
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.
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 ----------
- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++