洛谷P8567 真·基础数论问题

基础数论重定向

今天蒟蒻切水题切到一道建议评黄的红题，一下子给我整不会了……
题目传送门

理解题意

首先，我们要理解题意。
[JRKSJ R6] Nothing

我们定义 $f(x)$ 表示 $x$ 在 $2$ 进制下最低的 $1$ 的位置（你需要注意，二进制下的最低位是第 $0 $ 位）。以下是其在 C++ 语言中的代码（未考虑数据类型造成的问题）：

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

共有 $T$ 组询问，每组询问给定区间 $[l,r]$，求有多少个 $i\in [l,r]$ 使得 $f(i)< f(i+1)$。
打眼一看这啥呀？让我给你翻译翻译什么叫￥#@惊喜……
这题的意思就是：定义$f(x)=(n)max$ 使得 $x \ mod \ 2^n==0$
继续翻译：$f(x)$指的是数$x$的二进制的从右往左数的第一个$1$前面的$0$的个数。
还是不懂？我们来一套数据帮助理解：
我们这里有一个数：$114514$
我们将这个数转化成二进制：
$11011111101010010$
可以看到这个数的$f(x)$指的是数$x$的二进制的从右往左数的第一个$1$前面的$0$的个数是1。
而整道题的意思就是给定区间$[l,r]$要求出在这个区间符合$f(x) < f(x+1)$的$x$的个数。

思路

我们先看看数据规模哈：

数据规模

本题采用捆绑测试。

$\text{Subtask}$	$T\le$	特殊限制	$\text{Score}$
$1$	$10^5$	$l=r$	$10$
$2$	$10^4$	$r-l\le10^3$	$30$
$3$	$10^5$	$r\le10^6$	$20$
$4$	$10^5$	无	$40$

对于 $100\%$ 的数据，$1\le T\le 10^5$，$1\le l\le r\le 10^{18}$。

首先考虑一下，既然玩的是二进制，那我们敏锐的认为与奇偶性有关。
我们仔细研究后得出以下几条性质：

奇数后面一定是偶数，偶数后面一定是奇数（废话……）
对于任意偶数$x$，不满足$f(x) < f(x+1)$
对于任意奇数$x$，满足$f(x) < f(x+1)$

我们来看下怎么出来的：
首先奇数的二进制最右边一定是1，因为它无法被2整除。
然后偶数的二进制最右边一定是0，因为它能被2整除。
如果实在理解不了我们打一个奇偶数表来看看：

数字	二进制
$1$	$1$
$2$	$10$
$3$	$11$
$4$	$100$
$5$	$101$
$6$	$110$
$7$	$111$
$8$	$1000$
$9$	$1001$
$10$	$1010$

就能发现奇数末尾是1，偶数末尾是0。
这几个性质你可以细品品，就能发现，哇！
这道题我们已经 $O(1)$解决了！
怎么解决的？
对于一个区间$[l,r]$,我们找到其中奇数的个数就行了！。
怎么找呢？

代码T_T

请看代码：

#include<bits/stdc++.h>
using namespace std;
long long l,r,ans;
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%lld %lld",&l,&r);
		if(l==r){
			printf("%lld\n",l%2);
		}else{
			ans=0;
			if(l%2){
				ans++;
				l++;
			}	
			if(r%2){
				ans++;
				r--;
			}
			if(l>r){
				printf("%lld\n",ans);
			}else{
				printf("%lld\n",(r-l)/2+ans);
			}
		}
	}
	return 0;
}

思路大致是这样：