MENU

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

April 22, 2018 • Read: 98 • 算法

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=118,29,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;
}
Archives Tip
QR Code for this page
Tipping QR Code