2010年03月04日星期四.pku1395 && nwerc2001 Cog-Wheels 动态规划
这个题其实不难，首先将所有可能的比例用二重循环求出来，然后在1~10000范围内做dp，把所有
可能的乘积都求出来，然后再看看最后所求的比例化简之后得到的两个数是否都可达。
1 const int N = 64;
2 const int inf = 1 << 30;
3 int num[N], n, m, qa, qb;
4 const int M = 10010;
5 bool stat[M];
6
7 int gcd(int a, int b)
8 {
9 if (b==0) return a;
10 return gcd(b,a%b);
11 }
12
13 bool judge(int a, int b)
14 {
15 for (int i = 1; i * a < M && i * b < M; i++) {
16 if (stat[i * a] && stat[i * b]) {
17 return true;
18 }
19 }
20 return false;
21 }
22//http://www.cppblog.com/schindlerlee
23 int fac[M],top;
24 void pre()
25 {
26 int i, j, tmp;
27 scanf("%d", &n);
28 for (i = 0; i < n; i++) {
29 scanf("%d", num + i);
30 }
31 top = 0;
32 for (i = 0; i < n; i++) {
33 for (j = 0;j < n;j++) {
34 if (i == j) { continue; }
35 if (num[i] % num[j] == 0) {
36 fac[top++] = num[i] / num[j];
37 }
38 }
39 }
40 stat[1] = 1;
41 for (i = 0; i < top; i++) {
42 for (j = 1; j < M; j++) {
43 if (stat[j]) {
44 tmp = j * fac[i];
45 if (tmp < M) {
46 stat[tmp] = 1;
47 }
48 }
49 }
50 }
51 }
52
53 int main()
54 {
55 int testcase, testid, a, b;
56 scanf("%d", &testcase);
57 for (testid = 1; testid <= testcase; testid++) {
58 pre();
59 scanf("%d", &m);
60 printf("Scenario #%d:\n", testid);
61 while (m--) {
62 scanf("%d%d", &a, &b);
63 int d = gcd(a, b);
64 qa = a / d, qb = b / d;
65 if (judge(qa, qb)) {
66 printf("Gear ratio %d:%d can be realized.\n", a, b);
67 } else {
68 printf("Gear ratio %d:%d cannot be realized.\n", a, b);
69 }
70 }
71 putchar(10);
72 if (testid < testcase) {
73 memset(stat, 0, sizeof(stat));
74 }
75 }
76
77 return 0;
78 }
79