seuOJ580 - 数学高尔夫

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：2026 短码比赛

题目描述

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

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

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

将它们看作 $50$ 位的二进制数（含前导 $0$）。对于每个 $0 \le i \le 49$：

• 若 $A$ 的第 $i$ 个二进制位为 1，表示在坐标 $i$ 处有一个小球；
• 若 $B$ 的第 $i$ 个二进制位为 1，表示在坐标 $i+0.5$ 处有一个洞。

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

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

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

输入格式

一行两个整数 $A,B$（$0 \le A,B < 2^{50}$）。

输出格式

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

样例

样例 1 输入

31 16

样例 1 输出

1

样例 2 输入

480 31775

样例 2 输出

1

样例 2 解释

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

样例 3 输入

375299968947541 750599937895082

样例 3 输出

25