风灵无畏OI

https://pyoj.ml/problem/63

【题目描述】

众所周知，三巨头是明德中学信息奥赛中最有潜力的三位大佬，当我们还在玩泥巴的时候，他们已经会二进制了，现在，他们丢给了你这么一个问题。

三巨头创造了一种新的进制，叫做巨头进制，巨头进制转为十进制的计算方式是

∑ki=0(−1)i∗2i∗a[i]∑i=0k(−1)i∗2i∗a[i]

其中a[i]为该数在巨头进制下第i位的数，且a[i]∈{0,1}。

现在，三巨头给了你一个十进制数x，问你能否用巨头进制表示这个数。

【输入格式】

输入的第一行有一个整数 n，表示数据组数。

接下来n行，每行两个整数k,x，含义见题目描述。

 【输出格式】  

输出包括 n 行，每行一个字符串表示答案，如果x能被表示成巨头进制，则输出“YES”（不包含引号），否则输出“NO”（不包含引号）。

 【样例数据】

input1

2

2 2

1 2

output1

YES

NO

input2

2

16 602368

17 7018

output2

NO

YES

【数据范围与约定】

• 对于50%50%的数据，k≤20k≤20,

• 对于80%80%的数据，k≤40k≤40,

• 对于100%100%的数据，n≤200000,k≤60,x≤1018n≤200000,k≤60,x≤1018.

【时间限制】

1s空间限制：512MB

【题目分析】

       做这道题，其实弄清楚两个东西就好了。一个是模运算，另一个是负进制数。下面给出这两个相关内容的讲解（百度百科）：

模运算：https://baike.baidu.com/item/负进制数

负进制数：https://baike.baidu.com/item/模运算

      模运算的这篇，大家其实只要看这两个东西即可：

1 Turbo Pascal对mod的解释是这样的：

    A Mod B=A-(AdivB) * B （div含义为整除）[1] 

2 n % p得到结果的正负由被除数n决定,与p无关。例如：

      7%4 = 3， -7%4 = -3， 7%-4 = 3， -7%-4 = -3

   (在java、C/C++中%是取余，在python是模运算，此处%按取余处理)。

负进制数的那篇都看看就好。

     再回到本题上，你会发现，这就是看那个x能不能转换成一个负二进制数,而代码，刚刚百度百科上已经给出了。

【程序代码】

var  n,p,k,top,x:int64;

     i:longint;

begin

  readln(n);

  for i:=1 to n do

   begin

     readln(k,x); top:=-1;

     while x<>0 do

      begin

        inc(top);

        if top>k then break;

        p:=x mod -2; x:=x div -2;

        if p<0 then inc(x);

      end;

      if top<=k then writeln('YES') else writeln('NO');

   end;

end.

【解后反思】

        其实有些东西，靠平时自己的积累，你做得多了，对某些东西掌握越熟，对你就越有益。所以，就像锟哥大神说的那样，多做题就好了哈。

【特别鸣谢】

      感谢为本次考试出题的PB大佬！！！您永远是我们的红太阳！！！