題目很長(zhǎng)，就是說用從n種硬幣中選取4種不同的硬幣堆疊起來(lái)，作為桌子的四個(gè)腿，顯然，桌子的四個(gè)腿要相等。問對(duì)于一個(gè)給定的高度h，硬幣能夠堆成的不大于h的最大高度和不小于h的最小高度分別為多少？
應(yīng)為數(shù)據(jù)不大， n為50左右，可以用4個(gè)for循環(huán)來(lái)枚舉硬幣，假設(shè)四種硬幣為a、b、c、d，求的這四個(gè)數(shù)的最小公倍數(shù)即可，然后就用歐幾里得算法解決。
1
/**//*
2
Source Code
3
4Problem: 1855 User: yzhw
5Memory: 8648K Time: 313MS
6Language: G++ Result: Accepted
7
*/
8
9
10# include <iostream>
11# include <cstdio>
12using namespace std;
13int l[51];
14int refer[51][51][51][51];
15int gcd(int a,int b)
16
{
17 while(b)
18
{
19 int t=a%b;
20 a=b;
21 b=t;
22
}
23 return a;
24}
25int main()
26{
27 int n,t;
28 while(true)
29 {
30 scanf("%d%d",&n,&t);
31 if(!n&&!t) break;
32 for(int i=0;i<n;i++)
33 scanf("%d",l+i);
34 for(int a=0;a<n;a++)
35 for(int b=a+1;b<n;b++)
36 //if(a!=b)
37 for(int c=b+1;c<n;c++)
38 //if(a!=c&&b!=c)
39 for(int d=c+1;d<n;d++)
40 //if(a!=d&&b!=d&&c!=d)
41 {
42 int lcd1=l[a]*l[b]/gcd(l[a],l[b]),lcd2=l[c]*l[d]/gcd(l[c],l[d]);
43 int lcd=lcd1*lcd2/gcd(lcd1,lcd2);
44 refer[a][b][c][d]=lcd;
45
46 }
47
48 while(t--)
49 {
50 int minnum=0xfffffff,maxnum=-1;
51 int pos;
52 scanf("%d",&pos);
53 for(int a=0;a<n;a++)
54 for(int b=a+1;b<n;b++)
55 for(int c=b+1;c<n;c++)
56 for(int d=c+1;d<n;d++)
57 {
58
59 int lcd=refer[a][b][c][d];
60 if(pos-pos%lcd>maxnum)
61 maxnum=pos-pos%lcd;
62 if(pos%lcd&&lcd*(pos/lcd+1)<minnum)
63 minnum=lcd*(pos/lcd+1);
64 if(pos%lcd==0&&pos<minnum)
65 minnum=pos;
66
67 }
68 printf("%d %d\n",maxnum,minnum);
69 }
70 }
71 return 0;
72}
73
74