我来发一个比较难的题 看起来很简单 但是通过的人很低的

Cog-Wheels

--------------------------------------------------------------------------------

Time limit: 1 Seconds Memory limit: 32768K
Total Submit: 241 Accepted Submit: 11

--------------------------------------------------------------------------------

Background

Your little sister has got a new mechanical building kit, which includes many cog-wheels of different sizes. She starts building gears with different ratios, but soon she notices that there are some ratios which are quite difficult to realize, and some others she cannot realize at all. She would like to have a computer program that tells her what ratios can be realized and what ratios cannot. She asks you to write a program that does the job.

For example, let us assume that the kit contains cog-wheels with 6, 12, and 30 cogs. Your sister wants to realize a gear of ratio 5 : 4. One possible solution is shown in Figure 2.

Figure 2: Combination of cog-wheels realizing a gear of 5 : 4.

It depicts a complete gear of ratio 5 : 4. Four wheels are used: cog-wheels of sizes 30 and 12 on the first axis, cog-wheels of sizes 6 and 12 on the second axis. The gear ratio is given by

as desired. However, a gear of ratio 1 : 6 cannot be realized using the cog-wheels your sister has.

Problem

Given the sizes of the cog-wheels in the kit (i.e. the number of cogs they have), decide whether a given gear ratio can be built or not. You may use any finite number of cog-wheels of each size available.

Input

The input begins with a line containing the number of scenarios.

The input for each scenario starts with a description of the cog-wheels in the kit. First, there is a line containing the number n of different sizes of cog-wheels (1<=n<=20). The next line contains n numbers c1 . . . cn, separated by single blanks. These denote the n different sizes of the cog-wheels in the kit, with 5<=ci<=100 for i = 1, . . . , n. You may assume that there is a cog-wheel of smallest size c = min{c1, . . . , cn} in the kit such that all sizes c1, . . . , cn are multiples of c.

The line describing the available cog-wheels is followed by the list of gear ratios to be realized. It starts with a line containing the numbermof ratios. The nextmlines each contain two integers a and b, separated by a single blank. They denote the ratio a : b, with 1<=a, b<=10000.

Output

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print the results for all the gear ratios given in that scenario. For each gear ratio a : b, print a line containing either Gear ratio a:b can be realized.

or

Gear ratio a:b cannot be realized.

Terminate the output of each scenario with a blank line.

Sample Input

2
3
6 12 30
2
5 4
1 6
1
42
2
13 13
42 1

Sample Output

Scenario #1:
Gear ratio 5:4 can be realized.
Gear ratio 1:6 cannot be realized.

Scenario #2:
Gear ratio 13:13 can be realized.
Gear ratio 42:1 cannot be realized.

[此贴子已经被作者于2006-11-20 16:05:44编辑过]

应该是在说给定所需比例看是否存在这样的齿轮组合.

齿轮
----------------------------------------------------------------
时限:1秒 内存限制:32768k
Total Submit: 241 Accepted Submit: 11
----------------------------------------------------------------

背景：
你小妹妹取得了新的机械建设套件,其中包括许多大小不同的齿轮。她着手建立不同比率，但不久她发现有些比例很难实现，还有一些根本不能实现。她希望能有电脑程式可以告诉她什么比例可以实现，什么比列不能实现。她叫你写个程式来解决它。
举个例子，让我们假定套件包含齿轮60，12，30齿的。你妹妹要实现一个齿轮比率5：4。一个可行的办法，如图2所示。它描绘一个完整的齿轮比率5：4。使用四个轮子：30和12的齿轮在第一个轴，6和12的齿轮在第二个轴。齿轮比例按预期的实现了。不过，齿轮比为1:6用你妹妹手上的齿轮却不能实现。

问题：
根据套件中各种齿轮的大小(即齿数)判断齿轮比率是否可行。你可以使用任意大小（必须是套件中有的）的有限个齿轮。

输入：
开头一行表示共包含多少种情况。
每种情况开头是套件中包含的各种齿轮数。第一行是不同大小的齿轮的总数（1<=n<=20)；第二行有n个数c1,...cn（5<=ci<=100,i=1,2,...n)，由空格隔开，表示n个不同的齿轮数，你可以假设有一个最小的齿轮c＝min{c1,c2,...cn}，其余齿轮的齿数都是它的倍数。
接着的一行表示有多少比例需要实现。然后的每一行都有2个数a,b（也是空格隔开，且有1<=a,b<=10000），这表示比例a:b。

输出：
对每种情况的输出由"Scenario #i:"开始（i=1,2,...n），然后是每个比例能否实现。
注意2种情况之间空一行。

例子：
Sample Input

2
3
6 12 30
2
5 4
1 6
1
42
2
13 13
42 1

Sample Output

Scenario #1:
Gear ratio 5:4 can be realized.
Gear ratio 1:6 cannot be realized.

Scenario #2:
Gear ratio 13:13 can be realized.
Gear ratio 42:1 cannot be realized.

---------------------------------------------------------------
基本翻译完成，大家应该能看懂了吧。