青蛙跳跳算法问题


现在有这么一个有趣的问题。
青蛙在一个桌子上为了取得自己的食物,有以下规则。现在桌子上有一张卡片,卡片上写有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)。

输出
可以完成任务的卡片数。

c 算法

PengUin 12 years, 10 months ago

没理解错误的话,保证这N + 1个数的最大公约数是1就可以完成任务.

直接套N + 1层循环,穷举所有可能计算最大公约数,无疑可以解决问题,但是稍显笨重.

另一个想法是根据容斥原理,排除最大公约数不是1的情况.大概思路是计算出所有最大公约数被2整除的情况(即在2, 4, 6......2 * (M / 2)中任选N + 1)个, 被3整除的情况等等,然后减去其中重复的部分,即被6整除的,等等,最后即可得到卡片数.

初音的超甩葱炮 answered 12 years, 10 months ago

Your Answer