#P10835. 『FLA - I』冲云霄

    ID: 11687 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度普及− 上传者: 标签>数学洛谷原创O2优化位运算洛谷月赛

『FLA - I』冲云霄

背景

住在呼和浩特的小 R 很久以前就学会了异或。异或使用符号 ⊕\oplus 表示,在 C++ 中可用符号 ^ 表示。非负整数 xx 和 yy 的异或是指对它们二进制表示中的每一位进行如下运算得到的结果:

  • 若 xx 和 yy 的第 kk 个二进制位相同,结果的第 kk 个二进制位为 00;
  • 若 xx 和 yy 的第 kk 个二进制位不同,结果的第 kk 个二进制位为 11。

使用 (X)10(X)_{10} 表示十进制数 XX,(Y)2(Y)_2 表示二进制数 YY,因为 (12)10=(1100)2(12)_{10}=(1100)_2,(10)10=(1010)2(10)_{10}=(1010)_2,所以 $(12)_{10} \oplus (10)_{10}=(1100)_2 \oplus (1010)_2=(0110)_2=(6)_{10}$。

住在银川的小 F 想用这道题难倒小 R 但失败了,现在小 F 又想用这道题为难你,不能让他的阴谋得逞!

题目描述

给定整数 nn 和 mm,判断是否存在满足下列条件的数列 aa。本题中数列元素的下标从 11 开始。

  • 数列 aa 的长度为 mm,数列 aa 的每一项都为正整数。

  • a1⊕a2⊕⋯⊕am=na_1 \oplus a_2 \oplus \cdots \oplus a_m = n,即数列 aa 的所有项异或得到的结果等于 nn。

  • 数列 aa 中所有元素的值都相同。

输入格式

本题有多组测试数据。

第一行输入一个正整数 TT,表示测试数据组数。

对于每组测试数据,输入一行两个整数 n,mn,m。

输出格式

对于每组测试数据,输出一行一个字符串。如果存在满足条件的数列 aa,输出 Yes;否则输出 No。

4
3 3
2 5
0 3
1 4

Yes
Yes
No
No

提示

「样例解释 #1」

对于第一组测试数据,数列 aa 可以是 [3,3,3][3,3,3],此时 $a_1 \oplus a_2 \oplus a_3 = 3 \oplus 3 \oplus 3 = 3$。

对于第二组测试数据,数列 aa 可以是 [2,2,2,2,2][2,2,2,2,2],此时 $a_1 \oplus a_2 \oplus a_3 \oplus a_4 \oplus a_5 = 2 \oplus 2 \oplus 2 \oplus 2 \oplus 2 = 2$。

对于第三组和第四组测试数据,可以证明不存在满足条件的数列。

「数据范围」

测试点编号 T≤T \leq n≤n \leq m≤m \leq
1∼21 \sim 2 55 00 10910^9
3∼43 \sim 4 10910^9 33
55 10510^5 10910^9

对于所有测试数据,1≤T≤1051 \leq T \leq 10^5,0≤n≤1090 \leq n \leq 10^9,2≤m≤1092 \leq m \leq 10^9。