#580. 数学高尔夫

传统 1000 ms 256 MiB
标准 IO
文本比较 do_while_true 标签

题目描述

一遍又一遍地轻松取得短码竞赛(code golf)的胜利使你早已厌烦,你现在需要完成一个数学高尔夫(a.k.a. math golf)!

你有一个数轴,在上面你会先挖若干个洞,再放若干个球。

给定两个十进制整数 A,BA,B

将它们看作 5050 位的二进制数(含前导 00)。对于每个 0i490 \le i \le 49

  • AA 的第 ii 个二进制位为 1,表示在坐标 ii 处有一个小球;
  • BB 的第 ii 个二进制位为 1,表示在坐标 i+0.5i+0.5 处有一个洞。

所有小球同时向右滚动。一个小球会掉入它向右遇到的第一个洞中,并停止移动。请注意此时洞口没有被堵住,还有可能会落入小球。

若某个洞最终至少掉入了一个小球,则称这个洞被覆盖。

请你求出被覆盖的洞的数量。

输入格式

一行两个整数 A,BA,B0A,B<2500 \le A,B < 2^{50})。

输出格式

输出一个整数,表示被覆盖的洞的数量。

样例

样例 1 输入

31 16

样例 1 输出

1

样例 2 输入

480 31775

样例 2 输出

1

样例 2 解释

样例 2 中,前面的若干个洞都在所有小球左侧,因此不会被覆盖;后面第一个能遇到小球的洞会被覆盖。

样例 3 输入

375299968947541 750599937895082

样例 3 输出

25