「Mix it well!」
对于 Alice 来说,与 Shinobu 的初识,以及一同制作的曲奇饼,都将是她永远珍藏的回忆。
而 Shinobu 对于外国文化的强烈憧憬总能使她与 Alice 找到更多新奇的活动 —— 这次,是来自邻居国度的「花煎游戏」。
「花煎」来自于朝鲜半岛传统,以米饼上放置可食用的时花制成,而「花煎游戏」是指郊游踏青时采花制作花煎的活动,后来渐渐与源自中国的「重阳」习俗结合。
两人很快便兴致勃勃地开始了制作,不过 Alice 似乎很想在 Shinobu 面前展示自己最好的一面……
Alice 希望将自己制作的所有花煎摆成一个圆环形,并且使它们的色彩尽可能地丰富。由于 Alice 还要忙着制作,所以她把问题进行了一些抽象,希望擅长程序设计的你可以为她解决。
一个环由 个元素组成,顺时针标号为 至 ,其中 为不小于 Timeout waiting for MathJax: restarting 的偶数。每个元素都有一个颜色,且第 Timeout waiting for MathJax: restarting 个元素的颜色居下列二者之一:
定义一个环的色彩值为所有被「对立」元素分开的子段的长度乘积。换言之,将所有的「对立」元素移除,色彩值等于剩余的环上连续子段(包括长度为 的子段 —— 出现在两个「对立」元素相邻的情况下)的长度乘积。特别地,如果环上没有「对立」元素,那么其色彩值为 。
有些颜色似乎很像…… 不过确实是不同的。
输入的第一行包含一个正整数 —— 需要计算的 的个数。
接下来 行,每行包含一个正整数 —— 由于 可能很大,输入的值表示它的正平方根,即 。
输出 行 —— 对于每个输入的 输出一行,包含一个整数,表示色彩值不小于 的环最少包含的元素个数。当然啦,一定是个偶数。
4
5
10
221
1317
12
18
40
54
对于所有数据,有 ,。
Subtask # | 分值 | 的限制 | 的限制 |
---|---|---|---|
1 | |||
2 | |||
3 | |||
4 | ,且 ,其中 为正整数 | ||
5 | |||
6 |