最近Mayuyu遇到个神奇的数论题目,Mayuyu能做出来真的不容易啊,描述如下。
题目:给定一个正整数
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyN4EDNxYjMwIzMxUDM0EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
,满足条件
,以
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyN4EDNxYjMwIzMxUDM0EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
为根节点进行扩展,对于每一个节点
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyN4EDNxYjMwIzMxUDM0EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
,它只能到达能整除
它的节点
,如果存在节点
,使得
成立,则必定会经过
点,对于每一个节
点,有一个值
,这个值等于这个节点的最大深度,最后求输出每个节点的序号乘对应
值的和。
分析:对于一个数
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyN4EDNxYjMwIzMxUDM0EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
,它只能到达它的所有因子,所以第一步就是找出
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyN4EDNxYjMwIzMxUDM0EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
的所有因子,然后就是如果两个因子出现一
个能整除另一个的情况,就连一条边。最后就构建了一个图,在这个图中,我们从
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyN4EDNxYjMwIzMxUDM0EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
开始进行深度遍历,纪录
到达点
的最大深度值,最后加起来就可以了。这里采用链式前向星处理。
代码: