昨天教室里进来一只母猫,还很可爱的,被同学围着叫学姐(
埃及分数大家都很了解,是一个迭代加深搜索的经典题。
但是我突发奇想想到一个不用搜索(但是枚举)的做法。
很容易可以发现右边的式子通分之后的分母一定是式子左边约分后分母的倍数。
于是我们可以枚举右边式子通分后的分母,然后选取分数。
知道这个分母之后,我们只需要选取其各因数的倒数来相加得到左边,很容易发现这些分数通分之后的分子也是那个通分后的分母的因子(除其那个分母本身以外的其他因子都有)
于是我们可以把所有因子找出来跑个 dp,看看是否能够凑出左边式子通分后的分子。
里面应该是可以加各种优化的,但是我不会。
分析复杂度我也不会。
求评论一下。
标签:分数,20,2023.12,通分,因子,分母,式子 From: https://www.cnblogs.com/LiJoQiao/p/17916498.html