看完题目后，发现直接对 \(a\) 模拟操作的情况过多，不好处理。但如果对 \(n\) 进行逆向操作，似乎可以在很少步数内就变为 \(1\)。我们大胆猜想，用最少的步数使 \(n\) 变为 \(1\)，再考虑如何处理多余的次数（若次数不足则直接无解）。先列出转换后的操作：
- \(n\gets n + 1\)；
- \(n\gets n \div 2\)（注意，此处的 \(n\) 必须为偶数）。
不难发现，若 \(n\) 为偶数，则直接令 \(n\gets n \div 2\)；若 \(n\) 为奇数，则令 \(n \gets ( n + 1 ) \div 2\)。显然这是最快的方法。在缩减过程中统计最少次数，时间复杂度 \(O(\log_2 n)\)。
接下来考虑如何处理剩余的次数。我们可以通过模拟小数据，发现以下的两种循环：
- \(1\times2\div 2 = 1\)；
- \(2\times2-1-1=2\)。
操作一以 \(2\) 次操作为循环，操作二以 \(3\) 次操作为循环。因此若剩余次数大于 \(1\)，则必定有解。下面讨论剩余次数为 \(1\) 的情况。
前面已经证明了，\(1\) 次操作无法保持不变。因此，我们尝试将其加入到缩减过程中。具体地，设 \(n\) 为偶数（奇数进行一次操作会变成偶数），则有 $n \div 2 + 1 = ( n + 2 ) \div 2 = ( n + 1 + 1 ) \div 2 $。这样我们就成功地将 \(2\) 次操作变为 \(3\) 次操作。但是，观察式子可知，对于 \(n\) 为 \(2\) 的正整数次幂（或减一），这样做是不行的，读者可以根据运算顺序得到该结论。此时无解。
最后要注意 \(k=0\) 的情况以及其它代码实现的细节。
总时间复杂度 \(O(T\log_2 n)\)。
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
signed main()
{
int T,n,m,k,flag,pd;
cin >> T;
while( T -- )
{
m = 0;
flag = 0;
pd = 0;
cin >> k >> n;
if( n == 0 )
{
if( k ) cout << "Yes" << endl;
else cout << "No" << endl;
continue;
}
if( n == 1 )
{
if( k == 1 || k == 3 ) cout << "No" << endl;
else cout << "Yes" << endl;
continue;
}
while( n > 1 )
{
m ++;
if( n % 2 )
{
if( m == 1 ) flag = 1;
else flag = 0;
}
if( n % 2 ) n ++,pd = 1;
else n /= 2;
}
if( m > k || ( k - m == 1 && ( !pd || flag ) ) ) cout << "No" << endl;
else cout << "Yes" << endl;
}
return 0;
}