基础数论重定向
今天蒟蒻切水题切到一道建议评黄的红题，一下子给我整不会了……
题目传送门
理解题意
首先，我们要理解题意。
[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;
}
思路大致是这样：
- 如果l==r，那么直接输出l是否为奇数。
- 如果不相等
- 如果l为奇数，l+1，ans+1
- 如果r为奇数，r-1，ans+1
- 此时l，r一定都为偶数。
- 若l超过r直接输出ans
- 若没有，ans+(r-l)/2便是答案，这个自己推一下就好
完结撒花