#P1990. [Pku1395]Cog-Wheels

    ID: 1013 传统题 1000ms 512MiB 尝试: 8 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-试除法分解质因数线性不定方程行列式秩判定群广度优先搜索状态编码哈希表NorthwesternEurope2001

[Pku1395]Cog-Wheels

题目描述

Yeknom工作努力受到上司的赏识,作为奖赏上司奖励给Yeknom一个装有很多不同尺 寸的齿轮的工具箱。这样Yeknom就不用天天无所事事而可以尝试用不同的齿轮进行组合去 拼装不同的齿轮比了。 但是渐渐地,聪明的Yeknom发现不是所有的比例都是那么容易拼装出来的。有一些比 例甚至永远都无法拼装出来。于是Yeknom想知道给定一些特定的齿轮种类能否拼出 Yeknom想要的齿轮比例。 对于给定的一系列齿轮的种类(齿轮的种类仅由其齿的个数唯一确定) 和一系列给定比例。问是否有拼装方案满足比例。

输入格式

第一行:k表示数据组数。 对于每一组数据: 第一行一个整数n,表示齿轮的种数。 第二行n个整数,表示每种齿轮的齿数。 第三行一个整数m,表示比例数。 接下来m行每行两个数u,v,表示想要的比例为 u:v。

输出格式

对于每一组数据:

第一行输出 Scenario #A: 表示为第A组数据,接着对应每一个比例 u:v,如果可以拼装成功,输出 Gear ratio u:v can be realized. 否则 Gear ratio u:v cannot be realized.

每一组数据之间有一行空行。

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

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.

提示

K≤100K\leq 100 对于每组数据 N≤100,N\leq 100, M≤100,M\leq 100, 每种齿轮的齿数满足 1≤ci≤1001\le c_i\le100。设最小齿数为 c=min⁡{c1,c2,…,cn}c=\min\{c_1,c_2,\ldots,c_n\}。保证每个 cic_i 都是 cc 的倍数,即 c∣cic\mid c_i。每种齿轮都可重复使用任意有限次。 对于每个比例u:v,u<=10000,v<=10000 对于一个由两个齿轮组成的单位齿轮组,组成的比例是i:j其中i,j是两种齿轮的齿数。 对于两个齿轮组相连接而成的齿轮组,组成的比例是两个齿轮组比例的乘积。

题目来源

Northwestern Europe 2001