第五届蓝桥杯决赛B组C/C++——生物芯片

X 博士正在研究一种生物芯片，其逻辑密集度、容量都远远高于普通的半导体芯片。博士在芯片中设计了 n 个微型光源，每个光源操作一次就会改变其状态，即：点亮转为关闭，或关闭转为点亮。这些光源的编号从 1 到 n，开始的时候所有光源都是关闭的。博士计划在芯片上执行如下动作：

所有编号为 2 的倍数的光源操作一次，也就是把 2 4 6 8 ... 等序号光源打开

所有编号为 3 的倍数的光源操作一次, 也就是对 3 6 9 ... 等序号光源操作，注意此时 6 号光源又关闭了。

所有编号为 4 的倍数的光源操作一次。

.....

直到编号为 n 的倍数的光源操作一次。

X 博士想知道：经过这些操作后，某个区间中的哪些光源是点亮的。

输入格式

3 个用空格分开的整数：N L R (L<R<N<10^15) N 表示光源数，L 表示区间的左边界，R 表示区间的右边界。

输出格式

输出 1 个整数，表示经过所有操作后，[L,R] 区间中有多少个光源是点亮的。

样例

输入：5 2 3
输出：2

输入：10 3 6
输出：3

思路

这题模拟的方法做最好理解也最简单，但是数据太大，光源数不超过 10^15，根本开不出那么大的数组，所以只能找规律。

首先，题目告诉我们所有光源初始状态是关闭的，若想使其最终状态是打开的，很明显，要对每个灯泡进行奇数次操作，而操作的次数其实就是灯泡的因数个数，但是没有 “所有编号为 1 的倍数的光源操作一次”，所以因数个数要 - 1。最终结论就是，如果编号为 n 的灯泡，有偶数个因数，那么最终这个灯泡是打开的。比方说，编号为 6 的灯泡，他的因数是 1，2，3，6，四个因数，所以他最终是亮的状态。

其次，我们已知完全平方数有奇数个因数，比如 9，因数是 1，3，9。非完全平方数有偶数个因数，因为非完全平方数的因数一定是成对出现的，比方说 18，18=1*18，2*9，3*6

那么问题的答案就是给定区间 [L,R] 的非完全平方数的个数，区间 [L,R] 内的完全平方数的个数用 A 表示，非完全平方数的个数用 B 表示，则 B = （R-L+1）-A，（R-L+1）表示 [L,R] 这个区间内有多少个数字

对于给定的数 R，[1,R]内的完全平方数有 (int)sqrt(R)，则[L,R] 内的完全平方数个数 A = (int)sqrt(R) - (int)sqrt(L-1)，至于这里为什么是 L-1，原因很简单，因为 [L,R] 是闭区间，L 也包含在内，如果 L 本身就是个完全平方数，那么 (int)sqrt(R)-(int)sqrt(L) 就会少算一个完全平方数 L。由 A 我们可以得出 B = (R - L + 1) - ((int)sqrt(R) - (int)sqrt(L-1))

#include <bits/stdc++.h>
using namespace std; 
int main()
{
    long long int n,l,r,sum;
    cin>>n>>l>>r;
    sum = r - l + 1;
    long long int ll = (int)(sqrt(l-1));//减1是为了防止刚好边界是完全平方数 
    long long int rr = (int)(sqrt(r));//[1,r]内完全的平方数个数 
    cout<<sum - (rr - ll);
    return 0;
}