青蛙跳跳算法问题
现在有这么一个有趣的问题。
青蛙在一个桌子上为了取得自己的食物,有以下规则。现在桌子上有一张卡片,卡片上写有N+1个自然数。其中最后一个是M,而前N个数都不超过M,卡片上允许有相同的数字。青蛙每次可以任意选择卡片上一个数字,然后向前或者向后跳S步。青蛙最后的目的地是要跳到它前面一步,才可以吃到它的食物。
比如当N=2,M=18时,持有卡片(5, 12, 18)的跳蚤,就可以完成任务:他可以先向后跳5个单位长度,然后再连向后跳4次,每次12个单位长度,最后再向前连跳3次,每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤,不可能取得食物。
当确定N和M后,在这所有的卡片中,有多少张可以完成任务。
输入
两个整数N和M(N <= 15 , M <= 100000000)。
输出
可以完成任务的卡片数。
PengUin
12 years, 11 months ago