有一串有n颗珠子的项链,每颗珠子上有一个数字,从顺时针方向看依次是第1,2,…,n个珠子,第n个珠子之后是第1个珠子, 小G希望新的项链上的珠子尽可能多,问新项链上的珠子最多有多少个。
有一串有n颗珠子的项链,每颗珠子上有一个数字,从顺时针方向看依次是第1,2,…,n个珠子,第n个珠子之后是第1个珠子。但是小G觉得这串项链的造型不够美观,他决定用这串项链上的珠子造出一个新的项链,并且他希望这串新的项链是对称的。 一串项链是对称的,当且仅当存在至少一颗珠子满足:把它作为起始位置(即顺时针和逆时针方向数第0个珠子),对于任意的自然数i,顺时针数第i个珠子上的数字和逆时针数第i个珠子上的数字相同。特别的,一个仅有一颗珠子的项链也是对称的。 小G可以使用合成技术将任意正整数颗珠子合成为一个新的珠子,新珠子上的数字=原珠子上的数字的异或和。 用合成技术造出新项链的过程是这样的:最开始由小G确定一个能整除n的正整数k和一个原项链中的起始位置,之后从起始位置开始顺时针方向取连续的k个珠子,合成一个新的珠子作为新项链的第1个珠子,再取接下来连续的k个珠子,合成一个新的珠子作为新项链的第2个珠子,……,直到取完原项链的所有珠子为止。注意,合成的新珠子会直接放到新项链的位置,并不会插入原项链之中参与之后合成过程。新项链同样满足从顺时针方向看依次是第1,2,…,n个珠子,第n个珠子之后是第1个珠子。 小G希望新的项链上的珠子尽可能多,问新项链上的珠子最多有多少个。
标签: HBC14943小G的项链题解