编程介的小学生 2017-10-14 21:57 采纳率: 0.2%
浏览 1496
已采纳

Cow Math

Description

Taking their cue from the builders of the USA's Interstate Highway system, the cows have introduced the Interpasture Path numbering system. They have already numbered the N (2 <= N <= 25) pastures with the integers 1..N and now are numbering each path between two pastures with its own distinct Interpasture Path number in the range 1..2000
(e.g., I-9 and I-16).

In an example Interpasture Path map, four pastures numbered 1, 2, 3, and 4 are connected by Interpasture Paths I-3, I-6, I-9, and I-16:
4--< I-6>--2

             /         /

         < I-16>     < I-9>   

           /         /

          1--< I-3>--3  

Bessie likes to walk from pasture 1 to pasture 2 on the nifty new Interpasture system. During each walk, she never visits the same pasture twice, so possible walks on the sample map above are 1-4-2 and 1-3-2.

Over the years, Bessie has developed an amazing mathematical skill that she likes to exercise. During each walk, she enjoys finding the greatest common factor (GCF) of the Interpasture Paths that she traverses. For instance, the walk designated 1-4-2 touches I-16 and I-6 which have the greatest common factor of 2 (since 2 properly divides into 16 and 6 but no larger integer does).

As she walks the pastures day after day, she takes all the possible routes from pasture 1 to pasture 2 and remembers each of the GCFs. After she has taken every possible walk once, she computes the least common multiple (LCM) of all the GCFs. For this example, the two GCF values are 2 and 3 (GCF(6,16)=2 and GCF(3,9)=3), so the LCM is 6.

For large networks of paths, Bessie might get tired of all the walking, but she really wants to know the LCM for every map. Calculate that number for her.
Input

  • Line 1: N

  • Lines 2..N+1: These N lines represent the symmetric Interpasture Path connectivity matrix of the pastures. Line L shows the connectivity between pasture L-1 and the other pastures with its N space-separated integers. The first integer on each line is the Interpasture Path number that connects pasture L-1 and and pasture 1; the second integer is the IP number connecting pasture L-1 and pasture 2; etc. If pasture A connects to pasture B, then pasture B connects to Pasture A. When no Interpasture Path is available, the integer is 0.
    Output

A single line with a single integer that is the LCM of the GCFs of all the possible walks from pasture 1 to pasture 2. It is guaranteed that the answer will contain 100 or fewer digits.
Sample Input

4
0 0 3 16
0 0 9 6
3 9 0 0
16 6 0 0
Sample Output

6

展开全部

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-10-30 17:45
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
编辑
预览

报告相同问题?

悬赏问题

  • ¥30 SD中的一段Unet下采样代码其中的resnet是谁跟谁进行残差连接
  • ¥15 Unet采样阶段的res_samples问题
  • ¥60 Python+pygame坦克大战游戏开发实验报告
  • ¥15 R语言regionNames()和demomap()无法选中中文地区的问题
  • ¥15 Open GL ES 的使用
  • ¥15 我如果只想表示节点的结构信息,使用GCN方法不进行训练可以吗
  • ¥15 QT6将音频采样数据转PCM
  • ¥15 下面三个文件分别是OFDM波形的数据,我的思路公式和我写的成像算法代码,有没有人能帮我改一改,如何解决?
  • ¥15 Ubuntu打开gazebo模型调不出来,如何解决?
  • ¥100 有chang请一位会arm和dsp的朋友解读一个工程