牛客0X0001号：https://www.nowcoder.com/discuss/636123

求求赐个offer趴：【思路】（结果不一定对，忘记测试用例的结果了...） 1）解法：二叉树回溯+剪枝判断。 2）回溯： 2.1）对于参数L，遍历所有编码情况，共有2^L种。由于i=1对应的码字必须是Y（任何数字均是1的倍数），实际情况可缩减为2^L-1种； 2.2）回溯对象--树，为一颗二叉树，左节点为Y，右节点为N。 3）判断：（即判断当前编码是否合理） 3.1）编码具有依赖性，假设i<j，若1~i 的编码不合理，则1~j 的编码必定不合理（剪枝的基础）； 3.2）对于某个合理的编码CodeExample，将其1~L字符分成两个集合，A集合存储Y对应的位置，B集合存储N对应的位置。若CodeExmaple可对应数字x的编码，则有： 3.2.1）x是A集合里的任意元素的倍数，设A集合元素的最小公倍数是a，则x可以是a的最小公倍数； 3.2.2）x不可被B集合里的任意元素整除，设B集合元素的最小公倍数是b，则x与b的最大公约数是1，即x与b互质. 4）利用3.2.1与3.2.2这两条性质，对中间路径对应的编码进行判断： 4.1）gcd(~)函数求最大公约数，gcm(~)函数求最大公倍数； 4.2）对于位置i，preYGcm表示集合A（位置范围为1~i-1）中的a，preNGcm表示集合B的b，若a与b互质，则当前1~i-1的编码是合理的。