自动搬运

查看原文

来自洛谷，原作者为

	aimcf NOIP2024 rp++!

搬运于2025-08-24 22:40:13，当前版本为作者最后更新于2022-10-05 15:57:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这一篇题解的目标：让初学 OI 的蒟蒻也能理解这道题，并且拿到 $100$ 分的好成绩。

$\texttt{Part 0:}$ $f$ 函数的含义

int f(int x){
	int ans = 0;
	while (x % 2 == 0){
		x /= 2;
		ans += 1;
	}
	return ans;
}

进一步分析这个函数：

这是一个循环，当 $x\bmod 2 = 0$，也就是当 $x$ 是奇数的时候，停止循环并且返回计数器，否则进入循环，计数器自增 $1$，并且让 $x$ 除以 $2$。

蒟蒻：咦？这是什么？

那么这样解释：

将一个数 $x$ 转换成二进制，求 $x$ 的末尾有多少个连续的 $0$。

如果一个数 $x=11$，那么 $x$ 的二进制是 $(1011)_2$，容易发现末尾没有 $0$，也就是说，$f(11)=0$。

如果一个数 $x=12$，那么 $x$ 的二进制是 $(1100)_2$，容易发现末尾有两个 $0$。也就是说，$f(12)=2$。

由于 x /= 2 这一句话可以看做 x >>= 1，也就是将二进制右移一位。所以这个程序就是求解二进制的末尾有多少个连续的 $0$ 的。

进一步理解，x >>= 1 可以看做 x /= 2，那么求二进制的末尾有多少个连续的 $0$，就可以看做是求 $x$ 里面有多少个因子 $2$。

$\texttt{Part 1: Subtask \#1}$

在这一个 Subtask 里，$l=r$。也就是说，我们有一些不同的方法：

方法 $1$：直接判断 $f(l)$ 和 $f(l+1)$ 的大小。但是有一点麻烦，并且时间复杂度较高，是 $O(T\log x)$ 的。

方法 $2$：考虑 $f$ 函数的性质。

容易发现，如果 $x$ 是一个奇数，那么 $f(x)=0$。

原因：奇数没有因子 $2$。

同理，偶数有因子 $2$。所以 $f(x+1) > 0$。

因此，当 $l$ 为奇数的时候，$f(l) < f(l+1)$，否则，$f(l) > f(l+1)$。

由于奇数和奇数，偶数和偶数不会连续，所以没有 $f(l) = f(l+1)$ 的情况。

那么这一个 Subtask 可以在 $O(T)$ 的时间复杂度内完成。

$\texttt{Part 2: Subtask \#2}$

在这一个 Subtask 里，$r-l \le 10^3$，所以可以用 Subtask #1 的性质进行枚举。时间复杂度 $O(T\times (r-l))$。可以通过。

$\texttt{Part 3: Subtask \#3}$

在这一个 Subtask 里，$l\le r\le 10^6$。直接暴力枚举显然超时。

考虑使用前缀和进行优化。

蒟蒻：前缀和是什么？

假设有一个 $a$ 数列，那么考虑创建一个 $b$ 序列，满足 $b_i = b_i-1 + a_i$ 并且 $b_i = 0$，那么 $b$ 序列就是 $a$ 序列的前缀和序列。

区间求和问题：假设要求 $[l,r]$ 的和。

那么可以使用容斥原理。

$b_r$ 为 $[1,r]$ 区间的和，$b_{l-1}$ 为 $[1,l-1]$ 区间的和，那么 $b_r - b_{l-1}$ 的值就是 $[l,r]$ 区间的和。

时间复杂度 $O(1)$。模板题。

考虑进行预处理。

容易发现，$b_r = b_{r-1} + g(r)$，其中 $g(r)$ 判断的是 $r$ 是否为奇数。

然后询问区间 $[l,r]$ 只需要询问 $b_r - b_{l-1}$ 的值即可。

$\texttt{Part 4: Subtask \#4}$

$1\le l,r\le 10^{18}$，那么无法进行 $O(n)$ 的前缀和。

然后就需要使用性质。

• 奇数和偶数是交替的。
• 如果 $f(x) < f(x+1)$，那么一定有 $f(x + 1) > f(x + 2) < f(x + 3)$。

考虑特殊情况：$l=r$ 直接使用 Subtask #1 的性质，$l+1 = r$ 进行特殊判断。

然后考虑 $l\bmod 2 = 0$，$r\bmod 2 = 0$ 的特殊情况。

容易发现，$l$ 和 $r$ 此时都不满足 $f(x) < f(x+1)$ 的特殊性质。

那么这个时候直接使用公式 $\lfloor\frac{r-l}{2}\rfloor$ 即可算出答案。

那如果 $l\bmod 2 = 1$，$r\bmod 2 = 1$ 怎么办？

那么将 $l$ 进行右移一直到满足 $l\bmod 2 = 0$，并且答案 $+1$。

$r$ 同理，进行左移一直到满足 $r\bmod 2 = 0$，并且答案 $+1$。

实际上只需要进行 if 判断即可。这个地方一开始想复杂了，使用了 while 循环。

然后就可以在 $O(T)$ 的时间复杂度内通过这道题了！

超级大常数代码：

// 跑了 163ms
// 常数巨大
// 模拟赛因为常数 100->90 可以AFO了
#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main()
{
	int T;
	cin >> T;
	while (T --)
	{
		int l, r;
		cin >> l >> r;
		if (l == r)
			cout << l % 2 << '\n';
		else
		{
		    int ans = 0;
		    while (l % 2)
		    {
		        ans ++;
		        l ++;
		    }
		    while (r % 2)
		    {
		        ans ++;
		        r --;
		    }
		    if (l > r)
		        cout << ans << '\n';
		    else
		    {
		        ans += (r - l) / 2;
		        cout << ans << '\n';
		    }
		}
	}
	return 0;
}

注意点：不要忘记开 long long！十年 OI 一场空，不开 long long 见祖宗。