← 完整题目索引

PROJECT EULER · #0988

互不攻击的青蛙

Non-attacking Frogs

仅题目 · 已解决原题 ↗

青蛙可以放置在实数线上的整数位置。给定互质正整数 (a,b),每只青蛙都有能力沿正方向跳跃 ab 距离。

如果 m 处的青蛙可以通过一系列跳跃跳到 n,则放置在 mnm<n)处的两只青蛙正在攻击。例如,如果(a,b)=(3,5),则放置在011处的青蛙正在攻击,因为前者可以跳两次3和一次跳5到达11。然而,位于 411 的青蛙不会攻击。

非攻击性配置是放置任意数量的青蛙,使得:

  • 一只青蛙被放置在 0
  • 所有其他青蛙都被放置在不同的正整数处;
  • 没有两只青蛙在攻击。

F(a,b) 定义为每个青蛙的整数位置的总和,对所有非攻击配置进行求和。例如,如果(a,b)=(3,5),则有七个非攻击配置: {0}{0,1}{0,2}{0,4}{0,7}{0,1,2}{0,2,4}给予F(3,5)=23

您还将获得 F(5,13)=16336

查找 F(19,53)

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。