logo AlgoBeat OnlineJudge
登录 注册

#215917. 【MX-X26-T1】「Cfz Round 7」feel my soul

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

きっと誰もが ずっと探しているの / 想必每个人都在不停地寻找着

それは偶然ではなくて 偽りの愛なんかじゃなくて / 那并非偶然 也绝非虚假的爱


Yuki 有一条包含 个格子的环形纸带,每个格子的编号依次为

Yuki 打算给每个格子染上粉色或蓝色。Yuki 称一种染色方案是「鱼鱼」的,当且仅当:

  • 对于所有粉色格子,每个粉色格子左右两侧相邻的蓝色格子数量总和相等;
  • 对于所有蓝色格子,每个蓝色格子左右两侧相邻的粉色格子数量总和相等。

你需要求出「鱼鱼」的染色方案数。定义两种染色方案不同,当且仅当存在不大于 的正整数 ,满足格子 在两种染色方案中所染的颜色不同。

输入格式

本题有多组测试数据。

输入的第一行包含两个整数 ,分别表示该测试点所属的子任务编号和测试数据组数。样例满足

接下来依次输入每组测试数据。对于每组测试数据,共一行,包含一个整数

输出格式

对于每组测试数据,输出一行,包含一个整数,表示「鱼鱼」的染色方案数。

样例

样例输入 1

0 8
2
3
5
8
12
40
98
138

样例输出 1

4
8
2
8
14
8
4
10

数据范围与提示

样例 1 解释

对于第 组测试数据,「鱼鱼」的染色方案为粉粉、蓝蓝、粉蓝、蓝粉。

对于第 组测试数据,「鱼鱼」的染色方案为粉粉粉、粉粉蓝、粉蓝粉、蓝粉粉、粉蓝蓝、蓝粉蓝、蓝蓝粉、蓝蓝蓝。

对于第 组测试数据,「鱼鱼」的染色方案只有全粉和全蓝。

数据范围

对于所有测试数据,均有:

本题采用捆绑测试。

  • Subtask 1(12 points):
  • Subtask 2(32 points):保证 为质数。
  • Subtask 3(36 points):保证 为奇数。
  • Subtask 4(20 points):无特殊限制。