AdditionalFile7004.zip

#7004. 「THUPC 2026 初赛」序列

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

你要回答 $T$ 次询问，每次询问给定两个正整数 $n, m$，问是否能构造一个正整数序列 $a_{1}, a_{2}, \cdots a_{n}$ ，使得 $\exists 1 \leq j \leq n, a_{j}=m$ 且存在非负整数 $t$ 满足

$$\prod_{i=1}^{n}\left(a_{i}+a_{i+1}\right)=2^{2 t+1}$$

其中 $a_{n+1}=a_{1}$。

如果可以构造，则输出 YES，否则输出 NO。

输入格式

从标准输入读入数据。

第一行一个正整数 $T$ $\left(1 \leq T \leq 10^{6}\right)$ ，表示询问组数。

接下来 $T$ 行，每行两个正整数 $n, m$ $\left(1 \leq n \leq 2 \times 10^{6}, 1 \leq m \leq 2^{62}-1\right)$ ，表示你需要构造长度为 $n$ 的正整数序列，且序列中存在 $m$。

输出格式

输出到标准输出。

对于每组询问依次输出一行一个字符串，其为 YES 或 NO，表示对能否构造的判定。

样例

输入

2
3 3
2 1

输出

YES
NO

对于第一组询问，取 $a_{1}=1, a_{2}=3, a_{3}=1$ ，则 $(1+3) \times(3+1) \times(1+1)=32=2^{5}$ ，满足题设条件。

对于第二组询问，由 $\left(a_{1}+a_{2}\right)^{2}=2^{2 t+1}$ 无正整数解即知。

题目使用协议

来自 THUPC2026（2026年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2026 初赛 官方仓库（https://gitlink.org.cn/thusaa/thupc2026pre）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。