信息学集训队作业0049-wheel

1、题目0049 Wheel（齿轮）题目来源：Nwerc01推荐者：姜尚仆英文原文Cog-WheelsBackgroundYour 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 realiz

2、e, 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 siste

3、r 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 se

4、cond axis. The gear ratio is given byas desired. However, a gear of ratio 1 : 6 cannot be realized using the cog-wheels your sister has.ProblemGiven 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 fini

5、te number of cog-wheels of each size available.InputThe 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 l

6、ine 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 = minc1, . . . , cn in the kit such that all sizes c1, . . . , cn are multi

7、ples 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. OutputTh

8、e 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.orGear ratio

9、a:b cannot be realized.Terminate the output of each scenario with a blank line.Sample Input236 12 3025 41 6142213 1342 1Sample OutputScenario #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.中文翻译齿轮给定几种

10、齿数不同的齿轮，每一种齿轮都有无限多个，且最少的齿数是其他齿轮齿数的约数。现在要把它们通过连接成为齿轮组，实现一定的输入输出速率比，请问能否实现？输入首先是数据的组数。每组数据的第一行为齿轮的种数n，下面是每种齿轮的齿数ci。然后是问题的个数，下面是问题，询问前者a与后者b之比能否实现。齿轮的齿数为大于等于5小于等于100的整数，比例的分子分母均为不大于10000的整数。输出如果能实现，输出：”Gear ratio a:b can be realized.”，否则输出：”Gear ratio a:b cannot be realized.”。样例wheels.in236 12 3025 41

11、6142213 1342 1wheels.outScenario #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.初步讨论情况邵煊程需要先将齿数质因数分解，然后通过解方程组解决。陆可昱因为最少的齿数是其他齿轮齿数的约数，这使得分母或分子的因子个数不受限制。而这些数不是非常大，用搜索似乎就可以了。姜尚仆标准的方法是解方程，但是简化后的问题可以用宽搜解决

12、。简化后的问题的数学模型是：给定若干个整数，能否通过乘法和除法，得到目标分数。雷环中这道题和金牌之路解题指导P62上的是一样的。可以利用高斯消元的方法解决。问题的关键是将题目的模型变为线性方程组，另外还要注意处理中的无穷解和无解的情况。具体算法参看金牌之路解题指导P63 。张宁我们将齿轮的齿数分解质因数，100以内的质数有25个，齿轮i的齿数分解成ci=p1t1ip2t2ip25t25i。另外所求比例也能因数分解，若其中有大于100的质数则显然无解，否则也表示成幂乘积：则问题解可表示为a/b=c1x1c2x2cnxn，xi为正表示分子使用xi个ci，为负表示分母使用xi个ci，并且齿轮成对使用

13、，因此x1+x2+xn=0，因此我们即可列出方程组，利用高斯消元法来加以解决，若无解，则原问题无解，但是可能出现有多个待定变量，则我们需要搜索找到一组整数解，否则原问题无解。由于待定变量不多，因此搜索量不会很大。刘一鸣这道题和Gears一题惊人的相似，就是多了几个条件：其一，齿数很少，介于5和100之间；其二，最小齿数是其与所有齿数的约数（很重要）。有了这两个条件，我们不难想到一下的方法：为了充分利用第2个条件，我们可以先将的c1,c2,.,cn都除以cmin，得到d1,d2,.,dn，则必定有一个di为1。下面，我们比较一下，第2个条件到底有什么用呢？如果没有这句话，则分子、分母中的因数的个

14、数必须恰巧相等，如下所示：如果有了这句话，则分子、分母中的因数的个数就不一定相等了（必然由一个di为1，分子、分母上因数个数的差异可以用添加因数“1”的方法解决），如下所示：由上面的比较，我们可以得到下面的结论：如果比率R可以得到，则比率R*di或R/di也可以得到。这就引导我们用BFS去将这个问题解决。我们可以利用上面的结论，在预处理时将能得到的10000以内的整数比率全都求出来。然后，每读入一个比率a:b，就先将a、b约分得到a、b，如果整数比率a:1和b:1都可以得到（这个工作预处理时就完成了），则比率a:b可以得到，所以a:b也可以得到。也许有人会说，这种方法是有漏洞的：如果R*a*b

15、/c这种比率不能用其他方法求出，而R*a*b又大于10000，就会造成漏解。这时，第1个约束条件就起作用了：5=ci=100。所以，1=di=20。而这种算法会枚举10000以内的比率，所以，隐患自然而然地就被消除了。事实上，我在编完程序以后想到了这一点，以为程序错了，就抱着试试看的心理在zju提交，结果0.04秒AC。于是我又仔细看了一下题目，才发现程序没有错。林希德因为所求比率的分子分母均不超过10000，所以有人跟我说可以用BFS在预处理时求得1.10000范围为的所有可达整数比率，然后将所求比率a:b约分至最简形式a:b，转而判断整数比率a:1和b:1是否分别可达。我用此方法在Zju上尝试，果然00:00.08s就