当前位置:首页 > 递归 > 正文
NOI1.13-41判断元素是否存在
2454+

题目大意:给定k属于M,集合M的元素*2+1或者*3+1都属于集合M,问一个数x是否属于集合M。

题目描述

有一个集合M是这样生成的: (1) 已知 k 是集合 M 的元素; (2) 如果 y 是 M 的元素,那么, 2y+1 和 3y+1 都是 M 的元素; (3) 除了上述二种情况外,没有别的数能够成为 M 的一个元素。

问题:任意给定 k 和 x,请判断 x 是否是 M 的元素。这里的 k是无符号整数,x 不大于 100000, 如果是,则输出YES,否则,输出 NO

输入

输入整数 k 和 x, 逗号间隔。

输出

如果是,则输出 YES,否则,输出NO

样例输入

0,22

样例输出

YES

解题思路

如果x属于集合M,那么x等于k,或者(x-1)/2等于k,或者(x-1)/3等于k。如果不能整除,则不存在集合中的元素y推出x。

边界条件:x一直-1,一直/2、/3,会越来越小,如果出现负数或者小于k,都不可能是M中的元素了,因为M中元素不可能出现比k小的!

程序实现

About

坚决不Copy代码!

本文标签:,,,,

NOI1.13-41判断元素是否存在:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!