P8567

aimcf · 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] 的和。

那么可以使用容斥原理。