2010年03月04日星期四.pku1395 && nwerc2001 Cog-Wheels 動態(tài)規(guī)劃
這個題其實(shí)不難，首先將所有可能的比例用二重循環(huán)求出來，然后在1~10000范圍內(nèi)做dp，把所有
可能的乘積都求出來，然后再看看最后所求的比例化簡之后得到的兩個數(shù)是否都可達(dá)。
?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.shnenglu.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?