P14838 [THUPC 2026 初赛] 序列

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）初赛。 题解等资源可在 查看。

你要回答 $T$ 次询问，每次询问给定两个正整数 $n, m$，问是否能构造一个正整数序列 $a_1, a_2, \cdots, a_n$，使得 $$ \exists\, 1 \le j \le n,\ a_j = m $$ 且存在非负整数 $t$ 满足 $$ \prod_{i=1}^{n} (a_i + a_{i+1}) = 2^{2t+1} $$ 其中 $a_{n+1} = a_1$。 如果可以构造，则输出 `YES`，否则输出 `NO`。

从标准输入读入数据。 第一行一个正整数 $T$（$1 \le T \le 10^6$），表示询问组数。 接下来 $T$ 行，每行两个正整数 $n, m$（$1 \le n \le 2 \times 10^6,\ 1 \le m \le 2^{62} - 1$），表示你需要构造长度为 $n$ 的正整数序列，且序列中存在 $m$。

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

对于第一组询问，取 $a_1 = 1,\ a_2 = 3,\ a_3 = 1$，则 $$ (1+3) \times (3+1) \times (1+1) = 32 = 2^5 $$ 满足题设条件。 对于第二组询问，由 $(a_1 + a_2)^2 = 2^{2t+1}$ 无正整数解即知。