天天看点

数论vs图论

最近Mayuyu遇到个神奇的数论题目,Mayuyu能做出来真的不容易啊,描述如下。

题目:给定一个正整数

数论vs图论

,满足条件

数论vs图论

,以

数论vs图论

为根节点进行扩展,对于每一个节点

数论vs图论

,它只能到达能整除

     它的节点

数论vs图论

,如果存在节点

数论vs图论

,使得

数论vs图论

成立,则必定会经过

数论vs图论

点,对于每一个节

     点,有一个值

数论vs图论

,这个值等于这个节点的最大深度,最后求输出每个节点的序号乘对应

数论vs图论

值的和。

分析:对于一个数

数论vs图论

,它只能到达它的所有因子,所以第一步就是找出

数论vs图论

的所有因子,然后就是如果两个因子出现一

     个能整除另一个的情况,就连一条边。最后就构建了一个图,在这个图中,我们从

数论vs图论

开始进行深度遍历,纪录

     到达点

数论vs图论

的最大深度值,最后加起来就可以了。这里采用链式前向星处理。

代码: