埃及分数 Egyptian Fractions (HARD version)

- 给定一个分数 $\dfrac{a}{b}$，然后给定 $k$ 个数 $q_i$。 - 要求把 $\dfrac{a}{b}$ 分为几个不同的分子为 $1$ 的最简分数，要求分成的分数的分母中不能出现 $q_i$。 - 若有多种情况，输出拆分出分数最少的一种。 - 如果还有多种情况，应使第一大的分母最小，如果还不行，第二大最小，以此类推。 - **本题有 $t$ 组数据，** $t \le 100$。 - 其他数据范围：$2 \le a < b \le 876$，$0 \le k \le 5$，$\gcd(a,b)=1$，$2 \le q_i \le 1000$。

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=441&page=show_problem&problem=4003 [PDF](https://uva.onlinejudge.org/external/125/p12558.pdf) 



5
2 3 0
19 45 0
2 3 1 2
5 121 0
5 121 1 33

Case 1: 2/3=1/2+1/6
Case 2: 19/45=1/5+1/6+1/18
Case 3: 2/3=1/3+1/4+1/12
Case 4: 5/121=1/33+1/121+1/363
Case 5: 5/121=1/45+1/55+1/1089